题意：连续的几个颜色相同的格子称为一个连通块。选一个点为起点，每个操作是把所在连通块变一个颜色，求把整个区间染成同色需要的最少操作数。（注意，每次只能改变所在连通块的颜色，不能任选连通块，除了最开始时）
题解：
对于区间[L,R],最优的方案要么是全变成L处的颜色，要么全变成R处的颜色
因为可以看作是先选一个格子为起点，然后不断地将当前所在联通块与相邻格子合并，合并后一定是相邻格子的颜色才最优
那么，设f(i,j,0/1)表示区间[i,j]变为i/j处的颜色的最少操作次数
f(i,j,0)由f(i+1,j,0/1)转移来，f(i,j,1)由f(i,j-1,0/1)转移来，转移附加个颜色是否相同就行了，见代码。
#include<bits/stdc++.h> using namespace std ; #define ll long long int a[5001],dp[5001][5001][2]; int main() { int n; scanf("%d",&n); int cnt=0; for(int i=1 ; i<=n ; i++) { int x; scanf("%d",&x); if(x!=a[cnt]) { a[++cnt]=x; } } n=cnt; for(int k=2 ; k<=n ; k++) { for(int i=1 ; i<=n ; i++) { int j=i+k-1; if(j>n) break; dp[i][j][0] = min(dp[i+1][j][0]+(a[i]!=a[i+1]) , dp[i+1][j][1]+(a[i]!=a[j])); dp[i][j][1] = min(dp[i][j-1][0]+(a[i]!=a[j]) , dp[i][j-1][1]+(a[j-1]!=a[j])); } } printf("%d ",min(dp[1][n][0],dp[1][n][1])); }
滚动数组
#include<bits/stdc++.h> using namespace std; const int N=5001; int n,f[N][N],bf[N],cnt,ans,pre[N][3],fore[N][3]; int main() { // freopen("in.in","r",stdin); // freopen("2.out","w",stdout); scanf("%d",&n); cnt++; scanf("%d",&bf[cnt]); for(int i=2;i<=n;i++) { int tem; scanf("%d",&tem); if(tem!=bf[cnt]) { cnt++; bf[cnt]=tem; } } for(int k=3;k<=cnt;k++) { for(int i=1;i<=cnt-k+1;i++) { f[i][k]=max(fore[i+k-2][(k-2)%3],max(pre[i+1][(k-2)%3],f[i][k])); if(bf[i]==bf[i+k-1])f[i][k]++; pre[i][k%3]=max(pre[i][(k-1)%3],f[i][k]); fore[i+k-1][k%3]=max(fore[i+k-1][(k-1)%3],f[i][k]); } } int ans=max(pre[1][cnt%3],fore[cnt][cnt%3]); ans=cnt-1-ans; printf("%d ",ans); return 0; }
还有一种方法是：先把初始颜色序列去重，设去重后长度为n，然后找最长回文子序列len，答案就是n-ceil(len/2)。
因为对于一个回文子序列，只需操作floor(len/2)次，非回文序列长度为n必须两两合并共n-1次，因为起点可以任选，所以选最长回文子序列的中点作为起点，共操作n-ceil(len/2)次。
---------------------
原文：https://blog.csdn.net/Wen_Yongqi/article/details/86989782