Codeforces Round #538 (Div. 2)D（区间DP，思维）

#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;

巴特西

Codeforces Round #538 (Div. 2)D（区间DP，思维）

最新文章

热门文章