学步园

题意:

一块玉米地,有的位置不能种草,种草的小方格不能有临边. 问有多少种方案.

思路:

状压DP.

dp[ i ][ j ] 表示从上到下处理到第 i 行时, 该行状态为 j 的方案数.

下一行某状态的方案数就是上一行所有合理状态的方案数之和.

注意初始化和最后一行的处理.

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 14;
const int MOD = 1e8;
typedef long long ll;
int pat[MAXN],m,n;
ll dp[MAXN][1<<MAXN];
inline bool valid(int s,int i)
{
    return (s & (~pat[i]))?false:true;
}
inline bool adj(int s)
{
    for(int i=0;i<n-1;i++)
    {
        if((1<<i)&s && (1<<(i+1))&s)    return true;
    }
    return false;
}
void DP(int i, int s)
{
    for(int j=0;j<(1<<n);j++)
    {
        if(!valid(j,i-1) || (s&j) || adj(j))  continue;
        dp[i][s] += dp[i-1][j];
    }
    dp[i][s] %= MOD;
}

int main()
{
    scanf("%d %d",&m,&n);
    dp[0][0] = 1;
    for(int i=1;i<=m;i++)
    {
        int t;
        for(int j=n-1;j>=0;j--)
        {
            scanf("%d",&t);
            if(t)   pat[i] += 1<<j;
        }
        for(int j=0;j<(1<<n);j++)
        {
            if(!valid(j,i)||adj(j))   continue;
            DP(i,j);
        }
    }
    DP(m+1,0);
    printf("%d",(int)dp[m+1][0]);
}

131007重写:

行标号1-m, 列标号1-n.

dp[i][state]表示处理了1-i行时, 且第i行为state排布时, 一共的方案数.

可以枚举前面的更新后面的, 也可以枚举后面的然后找前面可行的加起来...第一种其实是不需要的, 因为前面不可行的方案数自然是0, 不判断的话也没有影响.

后面的需要满足:

1. 横向不相邻(不同时为1) 2. pat中0的位置不可取(&==0) 3. 与上一行不相邻(~&==0)

先找出后面的可行状态, 再Σ前面不矛盾的状态的方案数. 因为后面的状态需要额外判断本身, 因此枚举后面的.

864K 16MS ..效率低了..

上面的是

440K 0MS...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 15;
const int MOD = 100000000;
int n,m,pat0,pat[MAXN];
ll dp[MAXN][1<<12];
int main()
{
    while(scanf("%d %d",&m,&n)==2)
    {
        memset(pat,0,sizeof(pat));
        for(int i=1;i<=m;i++)
            for(int j=0;j<n;j++)
            {
                scanf("%d",&pat0);
                if(!pat0)   pat[i] |= 1<<j;//1==forbiden
            }
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(int i=1;i<=m;i++)//枚举行
            for(int state=0;state<1<<n;state++)//枚举当前状态
                if((state&pat[i])==0)//符合题设
                {
                    int k;
                    for(k=1;k<n;k++)//横向不相邻
                        if(((state>>k)&1) & ((state>>(k-1))&1))  break;
                    if(k!=n)    continue;
                    for(int s=0;s<1<<n;s++)//枚举上一行可行的
                        if(dp[i-1][s] && (state&s)==0)
                            dp[i][state] += dp[i-1][s];

                }
        for(int s=0;s<1<<n;s++)
            dp[m+1][0] += dp[m][s];
        printf("%d\n",(int)(dp[m+1][0]%MOD));
    }
}

调用函数判断大概比较快><