BZOJ 2331 [SCOI2011]地板 ——插头DP

【题目分析】

经典题目，插头DP。

switch 套 switch 代码瞬间清爽了。

【代码】

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define maxn 400005

const int md=20110520;

int dp[2][maxn],a[101][101],n,m,fac[15],tot,b[15];

char s[105];

void print(int x){F(i,0,m) printf("%d",(x%fac[i+1])/fac[i]);}

int main()

{

    scanf("%d%d",&n,&m);

    F(i,0,n-1){scanf("%s",s);F(j,0,m-1)a[i][j]=s[j]=='*'?1:0;}

    if (m>n){F(i,0,m-1)F(j,i+1,m-1)swap(a[i][j],a[j][i]);swap(m,n);}

//  F(i,0,n-1){F(j,0,m-1)printf("%d ",a[i][j]);printf("\n");}

    fac[0]=1;F(i,1,13)fac[i]=fac[i-1]*3;tot=fac[m+1]-1;

    int now=1,pre=0;

    memset(dp[now],0,sizeof dp[now]);

    dp[now][0]=1;

    F(i,0,n-1) F(j,0,m-1)

    {

        if (a[i][j])

        {

            now^=1;pre^=1;

            memset(dp[now],0,sizeof dp[now]);

            F(s,0,tot) if (dp[pre][s])

            {

//              printf("now is "); print(s); printf(" \n");

                int tmp1=(s%fac[j+1])/fac[j],tmp2=(s%fac[j+2])/fac[j+1],tmp=s;

                if (!tmp1&&!tmp2)

                {

                    (dp[now][s]+=dp[pre][s])%=md;

//                  printf(" to "); print(s); printf("\n");

                }

            }

        }

        else

        {

            now^=1;pre^=1;

            memset(dp[now],0,sizeof dp[now]);

            F(s,0,tot) if (dp[pre][s])

            {

//              printf("now is "); print(s); printf(" \n");

                int tmp1=(s%fac[j+1])/fac[j],tmp2=(s%fac[j+2])/fac[j+1],tmp=s;

                switch(tmp1)

                {

                    case 0:

                        switch(tmp2)

                        {

                            case 0:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp+2*fac[j]+2*fac[j+1]); printf("\n");

                                (dp[now][tmp+2*fac[j]+2*fac[j+1]]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp+fac[j]); printf("\n");

                                (dp[now][tmp+fac[j]]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp+fac[j+1]); printf("\n");

                                (dp[now][tmp+fac[j+1]]+=dp[pre][s])%=md;

                            break;

                            case 1:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp+fac[j]); printf("\n");

                                (dp[now][tmp+fac[j]]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp+2*fac[j+1]); printf("\n");

                                (dp[now][tmp+2*fac[j+1]]+=dp[pre][s])%=md;

                            break;

                            case 2:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp); printf("\n");

                                (dp[now][tmp]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp+2*fac[j]); printf("\n");

                                (dp[now][tmp+2*fac[j]]+=dp[pre][s])%=md;

                            break;

                        }

                    break;

                    case 1:

                        switch(tmp2)

                        {

                            case 0:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp+2*fac[j]); printf("\n");

                                (dp[now][tmp+2*fac[j]]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp+fac[j+1]); printf("\n");

                                (dp[now][tmp+fac[j+1]]+=dp[pre][s])%=md;

                            break;

                            case 1:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp); printf("\n");

                                (dp[now][tmp]+=dp[pre][s])%=md;

                            break;

                            case 2:

                            break;

                        }

                    break;

                    case 2:

                        switch(tmp2)

                        {

                            case 0:

                                tmp-=tmp1*fac[j]; tmp-=tmp2*fac[j+1];

//                              printf(" to "); print(tmp+2*fac[j]); printf("\n");

                                (dp[now][tmp+2*fac[j+1]]+=dp[pre][s])%=md;

//                              printf(" to "); print(tmp); printf("\n");

                                (dp[now][tmp]+=dp[pre][s])%=md;

                            break;

                            case 1:

                            break;

                            case 2:

                            break;

                        }

                    break;

                }

            }

        }

        if (j==m-1)

        {

//          printf("On The last of road\n");

            now^=1;pre^=1;

            memset(dp[now],0,sizeof dp[now]);

            F(s,0,tot) if (dp[pre][s])

            {

//              printf("End with "); print(s);

                int tmp=s,tmp1=(s%fac[m+1])/fac[m];

                if (tmp1) {continue;}

                tmp*=3;

//              printf(" can become "); print(tmp); printf("\n");

                (dp[now][tmp]+=dp[pre][s])%=md;

            }

        }

    }

    printf("%d\n",dp[now][0]);

}