Zuma

这个题没有素质!它卡常!

我发现网上很多人的题解都写得很奇怪，也不好确定正确性，所以我借这篇题解表达一下愚见

定义$ 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来质问我，发现这种做法好像是错的。。。

因为当三个相邻区间都出现2个1时，需要考虑消除顺序，答案好像会不同

但是我也没有正确性更高的做法了。。。

(希望我没有想错吧)

HDU 6212 Zuma

原文：https://www.cnblogs.com/chasedeath/p/11338917.html