一道状压DP裸题。
把种田的位置看作'1',之后预处理出来所有的‘1’位置不相邻的数,如果与不育土地重合,则舍弃这个状态。
上下不能相邻转化为与和为0.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
using namespace std;
const int mod=1e8,N=1<<12;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[13][378],num[378],a[13];
int main()
{
int n,m;qr(n),qr(m);
for(int i=0;i<1<<m;i++)
{
bool bk=1,cnt=0;
for(int j=0;j<m;j++)
{
if(i>>j&1)
{
if(cnt){bk=0;break;}
else cnt=1;
}
else cnt=0;
}
if(bk)num[++num[0]]=i;
}
for(int i=1;i<=n;i++)
for(int j=0,x;j<m;j++)
{
qr(x);if(x)a[i]|=1<<j;
}
//memset(f,0,sizeof(f));
for(int i=1;i<=num[0];i++)if((num[i]|a[1])==a[1])f[1][i]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=num[0];j++)
{
for(int k=1;k<=num[0];k++)
if(((num[j]&num[k])==0)&&((num[j]|a[i])==a[i])&&((num[k]|a[i-1])==a[i-1]))
f[i][j]=(f[i][j]+f[i-1][k])%mod;
}
int ans=0;
for(int i=1;i<=num[0];i++)
ans=(ans+f[n][i])%mod;
qw(ans);puts("");
return 0;
}
最后一次更新于2019-11-14
0 条评论