轮廓线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][];

int bit[][maxn];

bool legal(int x, int y,int mask)

{

    if (y==) if (bit[mask][y]&bit[mask][y+]) return ;

    for (int i=;i<y-;i++) if (bit[mask][i]&bit[mask][i+]) return ;

    for (int i=y;i<m;i++) if (bit[mask][i]&bit[mask][i+]) return ;

    return ;

}

int main()

{

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

    memset(a,,sizeof(a));

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

            scanf("%d",&a[i][j]);

    mb=(<<m)-;

    for (int mask=;mask<=mb;mask++)

    {

        int tmp=mask;

        for (int i=;i<=m;i++)

        {

            bit[mask][i]=tmp%;

            tmp/=;

        }

    }

    memset(f,,sizeof(f));

    f[][m][]=;

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

            for (int mask=;mask<=mb;mask++)

                if (legal(i,j,mask))

                {

                    int tmp=<<(j-);

                    if (j==)

                    {

                        f[i][j][mask&(~tmp)]+=f[i-][m][mask];

                        f[i][j][mask&(~tmp)]%=oo;

                        if (!bit[mask][j] && a[i][j])

                        {

                            f[i][j][mask|tmp]+=f[i-][m][mask];

                            f[i][j][mask|tmp]%=oo;

                        }

                    }

                    else

                    {

                        f[i][j][mask&(~tmp)]+=f[i][j-][mask];

                        f[i][j][mask&(~tmp)]%=oo;

                        if (!bit[mask][j] && a[i][j])

                        {

                            f[i][j][mask|tmp]+=f[i][j-][mask];

                            f[i][j][mask|tmp]%=oo;

                        }

                    }

                }

    int ans=;

    for (int mask=;mask<=mb;mask++)

        if (legal(n+,,mask))

        {

            ans+=f[n][m][mask];

            ans%=oo;

        }

    printf("%d\n",ans);

    return ;

}

Corn Fields

BZOJ 1087 Kings

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #define inf 1000000007

 #define oo 100000000

 #define maxn 11

 #define maxm 1050

 using namespace std;

 int n,m,mb;

 long long f[maxn][maxn][][maxm];

 int bit[maxm][maxn];

 bool legal(int x, int y,int mask)

 {

     if (y==)

     {

         if (bit[mask][n]&bit[mask][n+]) return ;

         if (bit[mask][n-]&bit[mask][n+]) return ;

     }

     else

     {

         if (bit[mask][y-]&bit[mask][n+]) return ;

         if (bit[mask][y-]&bit[mask][n+]) return ;

     }

     for (int i=;i<n;i++) if (bit[mask][i]&bit[mask][i+]) return ;

     return ;

 }

 int main()

 {

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

     mb=(<<(n+))-;

     memset(bit,,sizeof(bit));

     for (int mask=;mask<=mb;mask++)

     {

         int tmp=mask;

         for (int i=;i<=n+;i++)

         {

             bit[mask][i]=tmp%;

             tmp/=;

         }

     }

     memset(f,,sizeof(f));

     f[][n][][]=;

     for (int i=;i<=n;i++)

         for (int j=;j<=n;j++)

             for (int k=;k<=m;k++)

                 for (int mask=;mask<=mb;mask++)

                     if (legal(i,j,mask))

                     {

                         int tmp=<<(j-);

                         int ost=mask&(~tmp),nst=mask|tmp;

                         if (((mask>>(j-))&)!=((mask>>n)&)) ost^=(<<n),nst^=(<<n);

                         if (j==)

                         {

                             f[i][j][k][ost]+=f[i-][n][k][mask];

                             if (k && !bit[mask][j] && !bit[mask][j+] && !bit[mask][j-])

                                 f[i][j][k][nst]+=f[i-][n][k-][mask];

                         }

                         else

                         {

                             f[i][j][k][ost]+=f[i][j-][k][mask];

                             if (k && !bit[mask][j] && !bit[mask][j+] && !bit[mask][j-] && !bit[mask][n+])

                                 f[i][j][k][nst]+=f[i][j-][k-][mask];

                         }

                     }

     long long ans=;

     for (int mask=;mask<=mb;mask++)

         if (legal(n+,,mask))

         {

             ans+=f[n][n][m][mask];

         }

     printf("%lld\n",ans);

     return ;

 }

Kings