[POJ 3254] & [POJ 2411] & [POJ 1185]

3题都是状态压缩DP，难度是循序渐进的，便一起写了。

这题属于最基本的状态压缩DP。直接做的时候想了很久也不清楚如何构造DP，看了discuss后明白到，要使用位向量的形式表示一行的情况，并可以用&的方式判断是否能累加上一行的计数值。由此复杂度是O(m*2^n*2^n)，便能过了。这种题目太特殊了，某行的情况必须要在一个32位的int里放得下，并且每一行的向量总数不能太多，否则指数时间复杂度是难以承受的。但好像也没有别的办法可以有效求解这类问题。

#include<cstdio>
#include<cstring>

const int MOD=100000000;

int m,n,nt,b[12][12],dp[12][1<<12];

void calc(int i,int j,int d)
{
    if(j==n)
    {
        if(!i) dp[i][d]++;
        else
        {
            int k;
            for(k=0;k<nt;k++)
                if((d&k)==0) dp[i][d]=(dp[i][d]+dp[i-1][k])%MOD;
        }
        return;
    }
    if(b[i][j]&&(d&1)==0) calc(i,j+1,(d<<1)+1);
    calc(i,j+1,d<<1);
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&m,&n))
    {
        nt=1<<n;
        memset(dp,0,sizeof dp);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",&b[i][j]);
        for(i=0;i<m;i++)
            calc(i,0,0);
        for(i=j=0;i<nt;i++)
            j=(j+dp[m-1][i])%MOD;
        printf("%d\n",j);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

const int MOD=100000000;

int m,n,nt,b[12][12],dp[12][1<<12];

void calc(int i,int j,int d)

{

if(j==n)

{

if(!i) dp[i][d]++;

else

{

int k;

for(k=0;k<nt;k++)

if((d&k)==0) dp[i][d]=(dp[i][d]+dp[i-1][k])%MOD;

}

return;

}

if(b[i][j]&&(d&1)==0) calc(i,j+1,(d<<1)+1);

calc(i,j+1,d<<1);

}

int main()

{

int i,j;

while(~scanf("%d%d",&m,&n))

{

nt=1<<n;

memset(dp,0,sizeof dp);

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

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

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

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

calc(i,0,0);

for(i=j=0;i<nt;i++)

j=(j+dp[m-1][i])%MOD;

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

}

return 0;

}

Mondriaan’s Dream

和3254类似，但这里需要用^来判断竖直方块的情况（平行方块是00，垂直方块是1），并且记录的状态是亦或运算后的结果，这样才能反应下一层看到的上层情况，最后输出末行状态全0的计数值即可。

#include<cstdio>
#include<cstring>

int h,w,wt;
long long dp[11][1<<11];

void calc(int i,int j,int d)
{
    if(j>w) return;
    if(j==w)
    {
        if(!i) dp[i][d]++;
        else
        {
            for(int k=0;k<wt;k++)
                if((d^k)==d-k)
                    dp[i][d^k]+=dp[i-1][k];
        }
        return;
    }
    calc(i,j+1,(d<<1)+1);
    calc(i,j+2,d<<2);
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&h,&w)&&h)
    {
        wt=1<<w;
        memset(dp,0,sizeof dp);
        for(i=0;i<h;i++) calc(i,0,0);
        printf("%lld\n",dp[h-1][0]);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int h,w,wt;

long long dp[11][1<<11];

void calc(int i,int j,int d)

{

if(j>w) return;

if(j==w)

{

if(!i) dp[i][d]++;

else

{

for(int k=0;k<wt;k++)

if((d^k)==d-k)

dp[i][d^k]+=dp[i-1][k];

}

return;

}

calc(i,j+1,(d<<1)+1);

calc(i,j+2,d<<2);

}

int main()

{

int i,j;

while(~scanf("%d%d",&h,&w)&&h)

{

wt=1<<w;

memset(dp,0,sizeof dp);

for(i=0;i<h;i++) calc(i,0,0);

printf("%lld\n",dp[h-1][0]);

}

return 0;

}

炮兵阵地

和3254类似，但增加了难度：需要考虑前两行的情况，同时输出的是盘面最大值而不是计数值。虽然有前面两题的基础，但推状态转移时还是想了一下的：需要用一个dp[i][k][kk]形式的数组，记录第i行向量为k且i-1行向量为kk时的最值。由此便能在根据前两行的向量情况更新可行最值了。

但到这里为止算是出了思路，提交的时候还是分别被卡了内存和时间：内存方面，将dp改成滚动数组便ok了，时间方面，当构造第i行最值时记录其可行的解向量，这样到后面便可以根据记录下来的解情况来更新而无需枚举所有2^m*2^m种情况了。

#include<cstdio>
#include<cstring>

int n,m,mt,dp[2][1<<10][1<<10],hd[101],el;
char b[101][10],s[11];

struct E
{
    int d,p;
}e[1000000];

inline void adde(int i,int d)
{
    e[el].d=d; e[el].p=hd[i]; hd[i]=el++;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

void calc(int i,int j,int d,int c)
{
    if(j==m)
    {
        adde(i,d);
        if(i==1)
        {
            dp[i][0][d]=c;
        }
        else
        {
            int ii=i&1,iii=ii^1,l,ll,k,kk;
            for(l=hd[i-1];l!=-1;l=e[l].p)
            {
                k=e[l].d;
                for(ll=hd[i-2];ll!=-1;ll=e[ll].p)
                {
                    kk=e[ll].d;
                    if((d&k)+(d&kk)==0)
                        dp[ii][k][d]=max(dp[ii][k][d],
                                dp[iii][kk][k]+c);
                }
            }
        }
        return;
    }
    if(b[i][j]&&(d&3)==0) calc(i,j+1,(d<<1)+1,c+1);
    calc(i,j+1,d<<1,c);
}

int main()
{
    int i,j,k,l;
    while(~scanf("%d%d",&n,&m))
    {
        mt=1<<m;
        el=0;
        memset(dp,0,sizeof dp);
        memset(hd,-1,sizeof hd);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            for(j=0;j<m;j++)
                if(s[j]=='P') b[i][j]=1;
                else b[i][j]=0;
        }
        adde(0,0);
        for(i=1;i<=n;i++)
        {
            memset(dp[i&1],0,sizeof dp[i&1]);
            calc(i,0,0,0);
        }
        for(i=k=0;i<mt;i++)
            for(j=0;j<mt;j++)
                k=max(dp[n&1][i][j],k);
        printf("%d\n",k);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int n,m,mt,dp[2][1<<10][1<<10],hd[101],el;

char b[101][10],s[11];

struct E

{

int d,p;

}e[1000000];

inline void adde(int i,int d)

{

e[el].d=d; e[el].p=hd[i]; hd[i]=el++;

}

inline int max(int a,int b)

{

return a>b?a:b;

}

void calc(int i,int j,int d,int c)

{

if(j==m)

{

adde(i,d);

if(i==1)

{

dp[i][0][d]=c;

}

else

{

int ii=i&1,iii=ii^1,l,ll,k,kk;

for(l=hd[i-1];l!=-1;l=e[l].p)

{

k=e[l].d;

for(ll=hd[i-2];ll!=-1;ll=e[ll].p)

{

kk=e[ll].d;

if((d&k)+(d&kk)==0)

dp[ii][k][d]=max(dp[ii][k][d],

dp[iii][kk][k]+c);

}

return;

}

if(b[i][j]&&(d&3)==0) calc(i,j+1,(d<<1)+1,c+1);

calc(i,j+1,d<<1,c);

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

mt=1<<m;

el=0;

memset(dp,0,sizeof dp);

memset(hd,-1,sizeof hd);

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

{

scanf("%s",s);

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

if(s[j]=='P') b[i][j]=1;

else b[i][j]=0;

}

adde(0,0);

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

{

memset(dp[i&1],0,sizeof dp[i&1]);

calc(i,0,0,0);

}

for(i=k=0;i<mt;i++)

for(j=0;j<mt;j++)

k=max(dp[n&1][i][j],k);

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

}

return 0;

}