首页 > 代码库 > [ An Ac a Day ^_^ ] POJ 3254 Corn Fields 状压dp

[ An Ac a Day ^_^ ] POJ 3254 Corn Fields 状压dp

2024-08-18 07:47:53   213人阅读

题意：

有一块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


联系
我们