首页 > 代码库 > [ An Ac a Day ^_^ ] POJ 3254 Corn Fields 状压dp
[ An Ac a Day ^_^ ] POJ 3254 Corn Fields 状压dp
题意：
有一块n*m的土地
0代表不肥沃不可以放牛 1代表肥沃可以放牛
且相邻的草地不能同时放牛
问最多有多少种放牛的方法并对1e8取模
思路：
典型的状压dp 能状态压缩 能状态转移
能状态压缩的题的特点就是只有两种状态
所以用0 1表示两种状态 用位运算判断是否符合条件
然后将前一行的合理状态转移到后一行
最后统计最后一行的状态
dp[i][j]代表第i行以第j种状态放牛时有多少种不同的状态
（c++的语言特性是 封装 继承 多态~）
1 /* *********************************************** 2 Author :Sun Yuefeng 3 Created Time :2016/10/31 17:59:53 4 File Name :C.cpp 5 ************************************************ */ 6 7 #include<cstdio> 8 #include<iostream> 9 #include<algorithm>10 #include<cmath>11 #include<cstring>12 #include<string>13 #include<bitset>14 #include<map>15 #include<set>16 #include<stack>17 #include<vector>18 #include<queue>19 #include<list>20 #define M(a,b) memset(a,b,sizeof(a))21 using namespace std;22 typedef long long ll;23 const int inf=0x3f3f3f3f;24 const int maxn=1<<15;25 const int mod=1e8;26 int dx[8]= {0,0,1,-1,1,-1,1,-1};27 int dy[8]= {1,-1,0,0,-1,1,1,-1};28 29 int _map[maxn]; //记录给出的每块地的状态30 int st[maxn]; //记录每一行的状态31 int dp[15][maxn];32 33 bool judge(int x) //判断相邻两位是否同时为134 {35 return (x&(x<<1));36 }37 38 bool judge(int x,int y) //判断两位是否同时为139 {40 return _map[x]&st[y];41 }42 43 int main()44 {45 //freopen("in.txt","r",stdin);46 //freopen("out.txt","w",stdout);47 int n,m;48 while(cin>>n>>m){49 int x;50 M(dp,0),M(_map,0),M(st,0);51 for(int i=0;i<n;i++)52 {53 for(int j=0;j<m;j++)54 {55 cin>>x;56 if(!x)57 {58 _map[i]+=(1<<j); //向图中添加空地59 }60 }61 }62 int k=0;63 for(int i=0;i<(1<<m);i++) //初始化能不能以i状态放牛64 {65 if(!judge(i))66 {67 st[k++]=i;68 }69 }70 for(int i=0;i<k;i++) //初始化第一行状态71 {72 dp[0][i]=(!judge(0,i));73 }74 for(int i=1;i<n;i++)75 {76 for(int j=0;j<k;j++)77 {78 if(judge(i,j)) continue; //判断第i行是否能以j的方式放牛79 for(int l=0;l<k;l++)80 {81 if(judge(i-1,l)) continue; //判断上一行状态82 if(!(st[j]&st[l])) //符合题意转移状态83 dp[i][j]+=dp[i-1][l];84 }85 }86 }87 int ans=0;88 for(int i=0;i<k;i++)89 {90 ans+=dp[n-1][i];91 ans%=mod;92 }93 cout<<ans<<endl;94 } 95 return 0;96 }
[ An Ac a Day ^_^ ] POJ 3254 Corn Fields 状压dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。