题目大意：把一个只含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
      
       #include
       
        #include
        
         #include
         
          #include
          
           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 30233int a[maxn],f[maxn][5];#define inf 0x7fffffffint 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\n",min(ans1,ans2));    return 0;}