POJ 3254 状压DP

时间:2022-09-07 09:21:44

题目大意: 一个农民有一片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 ;
}