轮廓线DP POJ3254 && BZOJ 1087

补了一发轮廓线DP，发现完全没有必要从右往左设置状态，自然一点：

5 6 7 8 9

1 2 3 4

如此设置轮廓线标号，转移的时候直接把当前j位改成0或者1就行了。注意多记录些信息对简化代码是很有帮助的，尤其对于我这种代码经常错的一塌糊涂的人来说。。

呆马：

POJ 3254 Corn Fields

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define inf 1000000007
#define oo 100000000
#define maxn 15
#define maxm 5200

using namespace std;

int n,m,mb;
int a[maxn][maxn];
int f[maxn][maxn][5000];
int bit[5000][maxn];

bool legal(int x, int y,int mask)
{
    if (y==1) if (bit[mask][y]&bit[mask][y+1]) return 0;
    for (int i=1;i<y-1;i++) if (bit[mask][i]&bit[mask][i+1]) return 0;
    for (int i=y;i<m;i++) if (bit[mask][i]&bit[mask][i+1]) return 0;
    return 1;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(a,0,sizeof(a));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    mb=(1<<m)-1;
    for (int mask=0;mask<=mb;mask++)
    {
        int tmp=mask;
        for (int i=1;i<=m;i++)
        {
            bit[mask][i]=tmp%2;
            tmp/=2;
        }
    }
    memset(f,0,sizeof(f));
    f[0][m][0]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int mask=0;mask<=mb;mask++)
                if (legal(i,j,mask))
                {
                    int tmp=1<<(j-1);
                    if (j==1)
                    {
                        f[i][j][mask&(~tmp)]+=f[i-1][m][mask];
                        f[i][j][mask&(~tmp)]%=oo;
                        if (!bit[mask][j] && a[i][j])
                        {
                            f[i][j][mask|tmp]+=f[i-1][m][mask];
                            f[i][j][mask|tmp]%=oo;
                        }
                    }
                    else
                    {
                        f[i][j][mask&(~tmp)]+=f[i][j-1][mask];
                        f[i][j][mask&(~tmp)]%=oo;
                        if (!bit[mask][j] && a[i][j])
                        {
                            f[i][j][mask|tmp]+=f[i][j-1][mask];
                            f[i][j][mask|tmp]%=oo;
                        }
                    }
                }
    int ans=0;
    for (int mask=0;mask<=mb;mask++)
        if (legal(n+1,1,mask))
        {
            ans+=f[n][m][mask];
            ans%=oo;
        }
    printf("%d
",ans);
    return 0;
}

Corn Fields

BZOJ 1087 Kings

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <vector>
 7 #define inf 1000000007
 8 #define oo 100000000
 9 #define maxn 11
10 #define maxm 1050
11 
12 using namespace std;
13 
14 int n,m,mb;
15 long long f[maxn][maxn][88][maxm];
16 int bit[maxm][maxn];
17 
18 bool legal(int x, int y,int mask)
19 {
20     if (y==1)
21     {
22         if (bit[mask][n]&bit[mask][n+1]) return 0;
23         if (bit[mask][n-1]&bit[mask][n+1]) return 0;
24     }
25     else
26     {
27         if (bit[mask][y-1]&bit[mask][n+1]) return 0;
28         if (bit[mask][y-2]&bit[mask][n+1]) return 0;
29     }
30     for (int i=1;i<n;i++) if (bit[mask][i]&bit[mask][i+1]) return 0;
31     return 1;
32 }
33 
34 int main()
35 {
36     scanf("%d%d",&n,&m);
37     mb=(1<<(n+1))-1;
38     memset(bit,0,sizeof(bit));
39     for (int mask=0;mask<=mb;mask++)
40     {
41         int tmp=mask;
42         for (int i=1;i<=n+1;i++)
43         {
44             bit[mask][i]=tmp%2;
45             tmp/=2;
46         }
47     }
48     memset(f,0,sizeof(f));
49     f[0][n][0][0]=1;
50     for (int i=1;i<=n;i++)
51         for (int j=1;j<=n;j++)
52             for (int k=0;k<=m;k++)
53                 for (int mask=0;mask<=mb;mask++)
54                     if (legal(i,j,mask))
55                     {
56                         int tmp=1<<(j-1);
57                         int ost=mask&(~tmp),nst=mask|tmp;
58                         if (((mask>>(j-1))&1)!=((mask>>n)&1)) ost^=(1<<n),nst^=(1<<n);
59                         if (j==1)
60                         {
61                             f[i][j][k][ost]+=f[i-1][n][k][mask];
62                             if (k && !bit[mask][j] && !bit[mask][j+1] && !bit[mask][j-1])
63                                 f[i][j][k][nst]+=f[i-1][n][k-1][mask];
64                         }
65                         else
66                         {
67                             f[i][j][k][ost]+=f[i][j-1][k][mask];
68                             if (k && !bit[mask][j] && !bit[mask][j+1] && !bit[mask][j-1] && !bit[mask][n+1])
69                                 f[i][j][k][nst]+=f[i][j-1][k-1][mask];
70                         }
71                     }
72     long long ans=0;
73     for (int mask=0;mask<=mb;mask++)
74         if (legal(n+1,1,mask))
75         {
76             ans+=f[n][n][m][mask];
77         }
78     printf("%lld
",ans);
79     return 0; 
80 }

Kings