题目大意：把一个只含1,2,3的序列改成形如111……222……333……或333……222……111……的形式最少改几个数。
题解：光看这个数列无从知晓答案，所以试着采用DP。由于每个数变1,2,3与后面的数怎么变密切相关，所以F[i][j]表示前i个数中，第i个数变j后满足第一种形态的最少次数，则有F[i][j]=F[i-1][k]+diff(a[i],j)，其中k∈[1,j]，diff(a,b)表示a,b是否不同。形态2的话，既可以把上式的“i-1”改为“i+1”，又可以把整个序列前后颠倒再搞一次，非常自由。
代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cctype> using namespace std; int qread() { char c;int s=0; while (!isdigit(c=getchar())); do {s=s*10+c-'0';} while (isdigit(c=getchar())); return s; } int n; #define maxn 30233 int a[maxn],f[maxn][5]; #define inf 0x7fffffff int dif(int x,int y) { return (x==y?0:1); } void solve() { for (int j=1;j<=3;j++) f[0][j]=0; for (int i=1;i<=n;i++) for (int j=1;j<=3;j++) { f[i][j]=inf; int d=dif(a[i],j); for (int k=j;k;k--) f[i][j]=min(f[i][j],f[i-1][k]+d); } } int main() { n=qread(); for (int i=1;i<=n;i++) a[i]=qread(); solve(); int ans1=min(f[n][1],min(f[n][2],f[n][3])); for (int i=1;i<=n/2;i++) {int t=a[i];a[i]=a[n-i+1];a[n-i+1]=t;} solve(); int ans2=min(f[n][1],min(f[n][2],f[n][3])); printf("%d ",min(ans1,ans2)); return 0; }