题意：
一个颜色序列，每个位置有一个颜色，选择一个起始位置，每次可以改变包含这个位置的颜色段，将整个颜色段修改为任意一个颜色， 问最少操作多少次。n<=5000
思路：
区间dp。按照最少的原则，假设dp[i][j]已经是处理好的了， 那么由于要求最少，
那么这时候的颜色要么是a[i]色，要么是a[j]色，所以用dp[i][j][0/1]表示。把这一段变成a[i]/a[j]颜色的最少次数，
注意：
那么更新的时候要注意是d[i][j][0]由 dp[i+1][j]而来，dp[i][j][1]由dp[i][j-1][.]而来。
比赛时，由于多更新就wa了。。因为dp[i][j][x] 就已经知道 新加入的是i,还是j了
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) v.begin(),v.end() #define mem(a) memset(a,0,sizeof(a)) const int N = 5004; const ll mod =1e9+7; const int INF = 1e9+4; const double eps = 1e-7; int a[N],b[N]; string s; int n,m,t; int d[N][N][2]; int main(){ cin>>n; for(int i=1;i<=n;++i) cin>>a[i]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) d[i][j][0]=d[i][j][1]=INF; for(int i=1;i<=n;++i) d[i][i][0]=d[i][i][1]=0; for(int len=1;len<n;++len){ for(int i=1;i+len<=n;++i){ int j =i+len; //这里注意 不要多更新。 //d[i][j][0] = d[i][j-1][0]+(a[j]!=a[i]); //d[i][j][0] = min(d[i][j][0],d[i][j-1][1]+(a[j]!=a[j-1]) ); d[i][j][0] = min(d[i][j][0],d[i+1][j][0]+(a[i]!=a[i+1]) ); d[i][j][0] = min(d[i][j][0],d[i+1][j][1]+(a[i]!=a[j])); d[i][j][1] = d[i][j-1][1]+(a[j]!=a[j-1]); d[i][j][1] = min(d[i][j][1],d[i][j-1][0]+(a[j]!=a[i])); //d[i][j][1] = min(d[i][j][1],d[i+1][j][0]+(a[i]!=a[i+1])); //d[i][j][1] = min(d[i][j][1],d[i+1][j][1]+(a[i]!=a[j])); } } cout<<min(d[1][n][0],d[1][n][1])<<endl; return 0; }
原文：https://www.cnblogs.com/wjhstudy/p/10367210.html