这个题没有素质!它卡常!
我发现网上很多人的题解都写得很奇怪，也不好确定正确性，所以我借这篇题解表达一下愚见
定义$ dp[i][j][0...4]$表示
0:消完了
1:还剩1个0
2:还剩2个0
3:还剩1个1
4:还剩2个1
转移极其繁琐
卡常技巧:相邻相同的可以压成一个块
const int N=410; #define chk(a,b) (a>b&&(a=b)) //卡常 int n,m; char s[N]; int a[N],b[N],c[N],dp[N][N][5]; //0 --> 0 //1 --> one 0 //2 --> two 0 //3 --> one 1 //4 --> two 1 int main(){ int T; scanf("%d",&T); rep(kase,1,T){ scanf("%s",s+1); n=strlen(s+1); rep(i,1,n) a[i]=s[i]^'0'; int _n=0; rep(i,1,n) if(i==1||a[i]!=a[i-1]) { _n++; b[_n]=1; c[_n]=a[i]; } else b[_n]++,b[_n]=b[_n];//块合并 n=_n; rep(i,1,n) rep(j,1,n) rep(o,0,4) dp[i][j][o]=1e9; rep(i,1,n) { dp[i][i][c[i]*2+b[i]]=0; dp[i][i][0]=3-b[i]; }//边界条件初始化 drep(i,n,1) rep(j,i+1,n) { rep(k,i,j-1){ reg int *x=dp[i][k],*y=dp[k+1][j];//指针卡常 chk(dp[i][j][0],x[0]+y[0]); chk(dp[i][j][0],x[1]+y[2]); chk(dp[i][j][0],x[2]+y[2]); chk(dp[i][j][0],x[2]+y[1]); chk(dp[i][j][0],x[3]+y[4]); chk(dp[i][j][0],x[4]+y[3]); chk(dp[i][j][0],x[4]+y[4]); chk(dp[i][j][1],x[0]+y[1]); chk(dp[i][j][1],x[1]+y[0]); chk(dp[i][j][2],x[1]+y[1]); chk(dp[i][j][2],x[0]+y[2]); chk(dp[i][j][2],x[2]+y[0]); chk(dp[i][j][3],x[0]+y[3]); chk(dp[i][j][3],x[3]+y[0]); chk(dp[i][j][4],x[3]+y[3]); chk(dp[i][j][4],x[0]+y[4]); chk(dp[i][j][4],x[4]+y[0]); } chk(dp[i][j][0],dp[i][j][1]+2); chk(dp[i][j][0],dp[i][j][2]+1); chk(dp[i][j][0],dp[i][j][3]+2); chk(dp[i][j][0],dp[i][j][4]+1); } printf("Case #%d: %d\n",kase,dp[1][n][0]); } }(题解写到一半突然dalao来质问我，发现这种做法好像是错的。。。,但还不清楚是不是)
如果发现有错误请写评论
转载于:https://www.cnblogs.com/chasedeath/p/11338917.html
相关资源：JAVA上百实例源码以及开源项目