题目大意: 一个农民有一片n行m列 的农场 n和m 范围[1,12] 对于每一块土地 ,1代表可以种地,0代表不能种。 因为农夫要种草喂牛,牛吃草不能挨着,所以农夫种菜的每一块都不能有公共边。 告诉你 n ,m 和那些地方能种菜哪些地方不能种菜,求农夫一共有多少种方案种菜
解法:
基本思想是状压 也就是用一个int 型的数代表一行的种菜策略,二进制的0代表该位不能种菜,1位代表能种菜,使用位运算使处理速度变快
对于单行行,最多有2^12 种情况,并且 2^12种情况里面还有很多不满足题意的 筛选一下每行最多有400左右种情况,
1 先筛选出每行满足题意的情况
2 如何判断两行能否相邻? 如果一行状压的数使 i 另一行状压的数是 j 如果 i|j ==i+j 说明两行可以相邻
3 如何判断一个种法能否满足某一行的要求?
以样例来看
2 3
1 1 1
0 1 0
第一行二进制是7 第二行二进制是2
如果一个种菜的决策时 i 如果 i|2==2 就说明他能满足第二行的要求,,
然后就是dp[i][k] 代表第i行像k这样种菜的情况数
然后就是渣渣参考代码 g++
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <cstring>
#define CL(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define TEST cout<<"TEST ***"<<endl;
#define INF 0x7fffffff
#define MOD 100000000
using namespace std; ll dp[][];
int inn[],m,n;
int num[]; int initinn()
{
int i,j,preinn,nowinn,taginn;
CL(inn,);
for(i=;i<;i++)
{
preinn=,taginn=;
j=i;
while(j)
{
nowinn=j&;
if(nowinn==&&preinn==)
{
taginn=;
break;
}
preinn=nowinn;
j/=;
}
inn[i]=taginn;
}
i=;j=;
while(j<)
{
if(inn[j]==)
{
inn[i++]=j;
}
j++;
}
return i;
} using namespace std; int main()
{
initinn();
while(scanf("%d %d",&n,&m)!=EOF)
{
int i,j,k,ma=(<<m)-;
int a,sum;
CL(dp,);
for(i=;i<=n;i++)
{
sum=;
for(j=;j<m;j++)
{
scanf("%d",&a);
sum*=;
sum+=a;
}
num[i]=sum;
}
dp[][]=;
for(i=;i<=n;i++)
{
for(j=;inn[j]<=ma;j++)
{
if((inn[j]|num[i])!=num[i])continue;
for(k=;inn[k]<=ma;k++)
{
if((inn[j]|inn[k])==inn[j]+inn[k])
{
dp[i][j]+=dp[i-][k];
dp[i][j]%=MOD;
}
}
}
}
ll rem=;
for(i=;inn[i]<=ma;i++)
{
rem+=dp[n][i];
}
rem%=MOD;
printf("%I64d\n",rem);
}
return ;
}