首页 > 代码库 > POJ 3254-Corn Fields(状压DP)
POJ 3254-Corn Fields(状压DP)
题目链接:点击打开链接
第一发状压。。
题意:有一个n*m的牧场,1代表可以放牧,0代表不可以放牧,现在要求总的放牧方案,求中要求相邻的不能放牧(相邻代表上下左右,如果当前格的相邻格已经放牧了,此格就不能放牧了)
首先,为什么要状压? 比较容易想到的算法是深搜,从(1,1)搜到(n,m)枚举每个格子放或者不放,统计总方案,但仔细一想这种方法肯定行不同,n和m的范围最大是12*12
逐一枚举的话会达到O(2^(n*m))指数级的复杂度绝壁是渣到底了 那么换个思路,考虑每一行,单是1行的状态就达到了2^n种,好了,我们就看这2^n种状态,对于一行中的每一个格,放牧写成1,不放牧写成0,这样对应的二进制就每一种状态,首先,预处理,原先方格中为0的地方是不可以放牧的,所以把这些状态踢掉,其次是相邻的不能同时放牧,这样也可以踢掉不少状态,剩下的状态就是第一行的合法状态了,转到下一行时,注意处理上述一些不合法的状态就行了。
正着推:
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1<<15 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 100000000 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; int cur[15],dp[15][maxn],s[maxn],n,m,tot; void init() { int num=1<<m;tot=0; for(int i=0;i<num;i++) { if(i&(i<<1)) continue; s[tot++]=i; } } bool check(int x,int y) { if(x&y)return 0; return 1; } void solve() { memset(dp,0,sizeof(dp)); for(int i=0;i<tot;i++) if(check(s[i],cur[1])) dp[1][i]=1; for(int i=2;i<=n;i++) { for(int j=0;j<tot;j++) { if(!check(s[j],cur[i])) continue; for(int k=0;k<tot;k++) { if(!check(cur[i-1],s[k])) continue; if(!check(s[j],s[k])) continue; dp[i][j]=(dp[i][j]+dp[i-1][k])%Mod; } } } int ans=0; for(int i=0;i<tot;i++) ans=(ans+dp[n][i])%Mod; printf("%d\n",ans); } int main() { int tem; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { cur[i]=0; for(int j=1;j<=m;j++) { scanf("%d",&tem); if(tem==0) cur[i]+=1<<(m-j); } } init(); solve(); } return 0; }
上面参考的别人的代码,这个倒着搜是后来自己撸的。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1<<15 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 100000000 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; int cur[15],dp[15][maxn],s[maxn],n,m,tot; void init() { int num=1<<m;tot=0; for(int i=0;i<num;i++) { if(i&(i<<1)) continue; s[tot++]=i; } } bool check(int x,int y) { if(x&y)return 0; return 1; } int dfs(int num,int sta) { int& ans=dp[num][sta]; if(num==1) { if(check(cur[num],s[sta])) return ans=1; else return ans=0; } if(ans!=-1)return ans; ans=0; for(int i=0;i<tot;i++) if(check(s[sta],cur[num])&&check(s[i],cur[num-1])&&check(s[sta],s[i])) ans=(ans+dfs(num-1,i))%Mod; return ans; } int main() { int tem; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { cur[i]=0; for(int j=1;j<=m;j++) { scanf("%d",&tem); if(tem==0) cur[i]+=1<<(m-j); } } memset(dp,-1,sizeof(dp)); init();int ans=0; for(int i=0;i<tot;i++) ans=(ans+dfs(n,i))%Mod; printf("%d\n",ans); } return 0; }
POJ 3254-Corn Fields(状压DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。