http://tyvj.cpwz.cn/Problem_Show.asp?id=1625
# include<stdio.h># include<string.h>int min(int x,int y){if(x<=y) return x; return y;}int main(){int f[110][11][11][11]; int i,j,k,l,n; scanf("%d",&n);getchar(); int a[n+10];char t; for(i=1;i<=n;i++) {scanf("%c",&t);a[i]=t-'A'+1;getchar(); } for(i=0;i<=n;i++) for(j=0;j<=10;j++) for(k=0;k<=10;k++) for(l=0;l<=10;l++) f[i][j][k][l]=999999; int x=0,y=0,z=0; for(i=1;i<=10;i++) {//printf("%d\n",a[i]); if(a[i]==1) x++; else if(a[i]==2) y++; else if(a[i]==3) z++; } int ll,kk,xx,yy,zz; f[0][x][y][z]=0; for(i=0;i<=n;i++) {for(x=0;x<=10;x++) for(y=0;y<=10-x;y++) for(z=0;z<=10-x-y;z++) if(f[i][x][y][z]!=999999){ //printf("i:%d x:%d y:%d z:%d %d\n",i,x,y,z,f[i][x][y][z]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+x&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+x][xx][y+yy][z+zz]=min(f[i][x][y][z]+1,f[i+x][xx][y+yy][z+zz]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+y&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+y][x+xx][yy][z+zz]=min(f[i][x][y][z]+1,f[i+y][x+xx][yy][z+zz]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+z&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+z][x+xx][y+yy][zz]=min(f[i+z][x+xx][y+yy][zz],f[i][x][y][z]+1); } }int minn=999;int g; printf("%d\n",f[n][0][0][0]); return 0;}
//printf("i:%d x:%d y:%d z:%d %d\n",i,x,y,z,f[i][x][y][z]);这句注释去掉后答案会变。。求解
# include<stdio.h># include<string.h>int min(int x,int y){if(x<=y) return x; return y;}int main(){int f[110][11][11][11]; int i,j,k,l,n; scanf("%d",&n);getchar(); int a[n+10];char t; for(i=1;i<=n;i++) {scanf("%c",&t);a[i]=t-'A'+1;getchar(); } for(i=0;i<=n;i++) for(j=0;j<=10;j++) for(k=0;k<=10;k++) for(l=0;l<=10;l++) f[i][j][k][l]=999999; int x=0,y=0,z=0; for(i=1;i<=10;i++) {//printf("%d\n",a[i]); if(a[i]==1) x++; else if(a[i]==2) y++; else if(a[i]==3) z++; } int ll,kk,xx,yy,zz; f[0][x][y][z]=0; for(i=0;i<=n;i++) {for(x=0;x<=10;x++) for(y=0;y<=10-x;y++) for(z=0;z<=10-x-y;z++) if(f[i][x][y][z]!=999999){ //printf("i:%d x:%d y:%d z:%d %d\n",i,x,y,z,f[i][x][y][z]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+x&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+x][xx][y+yy][z+zz]=min(f[i][x][y][z]+1,f[i+x][xx][y+yy][z+zz]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+y&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+y][x+xx][yy][z+zz]=min(f[i][x][y][z]+1,f[i+y][x+xx][yy][z+zz]); xx=0;yy=0;zz=0; for(ll=i+11;ll<=i+10+z&&ll<=n;ll++) {if(a[ll]==1) xx++; else if(a[ll]==2) yy++; else zz++; } f[i+z][x+xx][y+yy][zz]=min(f[i+z][x+xx][y+yy][zz],f[i][x][y][z]+1); } }int minn=999;int g; printf("%d\n",f[n][0][0][0]); return 0;}
//printf("i:%d x:%d y:%d z:%d %d\n",i,x,y,z,f[i][x][y][z]);这句注释去掉后答案会变。。求解