首页 > 代码库 > POJ 3254 状压DP
POJ 3254 状压DP
题目大意： 一个农民有一片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 100000000using namespace std;ll dp[15][1000];int inn[4100],m,n;int num[12];int initinn(){ int i,j,preinn,nowinn,taginn; CL(inn,0); for(i=0;i<4100;i++) { preinn=0,taginn=1; j=i; while(j) { nowinn=j&1; if(nowinn==1&&preinn==1) { taginn=0; break; } preinn=nowinn; j/=2; } inn[i]=taginn; } i=0;j=0; while(j<4100) { if(inn[j]==1) { inn[i++]=j; } j++; } return i;}using namespace std;int main(){ initinn(); while(scanf("%d %d",&n,&m)!=EOF) { int i,j,k,ma=(1<<m)-1; int a,sum; CL(dp,0); for(i=1;i<=n;i++) { sum=0; for(j=0;j<m;j++) { scanf("%d",&a); sum*=2; sum+=a; } num[i]=sum; } dp[0][0]=1; for(i=1;i<=n;i++) { for(j=0;inn[j]<=ma;j++) { if((inn[j]|num[i])!=num[i])continue; for(k=0;inn[k]<=ma;k++) { if((inn[j]|inn[k])==inn[j]+inn[k]) { dp[i][j]+=dp[i-1][k]; dp[i][j]%=MOD; } } } } ll rem=0; for(i=0;inn[i]<=ma;i++) { rem+=dp[n][i]; } rem%=MOD; printf("%I64d\n",rem); } return 0;}
POJ 3254 状压DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。