Problem 6

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int dp[5010][5010][2],c[5010];
int main(){
    int n;
    scanf("%d",&n);
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++){
        scanf("%d",c+i);
        dp[i][i][0]=dp[i][i][1]=0;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(c[l]==c[r]){
                int curv;
                curv=min(dp[l+1][r][1],dp[l+1][r][0]+1);
                if(c[l+1]==c[l]) curv=min(curv,dp[l+1][r][0]);
                curv=min(curv,min(dp[l][r-1][0],dp[l][r-1][1]+1));
                if(c[r-1]==c[r]) curv=min(curv,dp[l][r-1][1]);
                dp[l][r][0]=dp[l][r][1]=curv;
            }else{
                int curv;
                curv=min(dp[l+1][r][0]+1,dp[l+1][r][1]+1);
                if(c[l+1]==c[l]) curv=min(curv,dp[l+1][r][0]);
                curv=min(curv,min(dp[l][r-1][0]+2,dp[l][r-1][1]+2));
                if(c[r]==c[r-1]) curv=min(curv,dp[l][r-1][1]+1);
                dp[l][r][0]=curv;
                curv=min(dp[l+1][r][0]+2,dp[l+1][r][1]+2);
                if(c[l]==c[l+1]) curv=min(curv,dp[l+1][r][0]+1);
                curv=min(curv,min(dp[l][r-1][0]+1,dp[l][r-1][1]+1));
                if(c[r]==c[r-1]) curv=min(curv,dp[l][r-1][1]);
                dp[l][r][1]=curv;
            }
        }
    }
    printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
    return 0;
}