Codeforces Round #538 (Div. 2)D(区间DP,思维)

时间:2024-08-17 19:33:20

#include<bits/stdc++.h>
using namespace std;
int a[5007];
int dp[5007][5007];
int main(){
    int n;
scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    n=unique(a+1,a+1+n)-a-1;
    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++){

    dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);//右面变为左面的颜色或者左面变为右面的颜色
             if(a[i]==a[j])
                dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);//里面变为外面的颜色
        }
    }
    printf("%d",dp[1][n]);
    return 0;