POJ 3254 Corn Fields 状态压缩
状态 压缩 poj fields
2023-09-11 14:20:46 时间
这题对我真的非常难。实在做不出来,就去百度了,搜到了一种状压DP的方法。这是第一种
详细见凝视
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; #define mod 100000000 int n,m,map[15];//map数组用来存图 int cnt[10000],dp[15][10000];//cnt存当一层每处都能够放置东西时,全部满足题意的情况 int k; bool ok(int x)//推断某种方法是否满足题意 { if(x&(x<<1)) return false; //假设某点左右有点的话,返回false return true; } void find() { for(int i=0;i<(1<<m);i++) //从0開始到1<<m。找到全部单层满足题意的情况 { if(ok(i)) cnt[k++]=i; } } int main() { int i,j,temp; while(cin>>n>>m) { memset(map,0,sizeof(map)); for(i=0;i<n;i++) { for(j=0;j<m;j++) { cin>>temp; if(!temp) map[i]|=1<<j;//此处存图应该注意。与题中相反的是,当某点不能够放置东西时,应该置为1。便于兴许操作 } } k=0; memset(dp,0,sizeof(dp)); memset(cnt,0,sizeof(cnt)); find(); for(i=0;i<k;i++)//初始化第一行 { if(!(map[0]&cnt[i])) { dp[0][i]=1; } } for(i=1;i<n;i++)//从第二行開始进行递推 { for(j=0;j<k;j++) { if(map[i-1]&cnt[j]) continue; for(int p=0;p<k;p++) { if((map[i]&cnt[p])||(cnt[p]&cnt[j])) continue; dp[i][p]=(dp[i][p]+dp[i-1][j])%mod; } } } int ans=0; for(i=0;i<k;i++)//算出全部的情况 { ans=(ans+dp[n-1][i])%mod; } cout<<ans<<endl; } return 0; }
另外一种方法是状态压缩+记忆化搜索。这是我从瓜神那看来的记忆化搜索,然后依据我从上个代码中学来的东西改进了下,QAQ。要学的东西还有非常多。慢慢来吧
主要思路是从第一层開始向下搜索,假设搜到符合条件的就继续向下搜索,直到最后一行为止
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; #define maxn 20 #define mod 100000000 int map[maxn]; int dp[maxn][1<<12]; int n,m; bool ok(int i,int state,int cur) { if(map[cur]&i) return false;//推断是否会把东西放在不能放东西的地方 if(i&(i<<1)) return false;//推断东西的左右是否放置了东西 if(cur) { if(state&i) return false;//推断东西的上边是否放置了东西 } return true; } int dfs(int cur,int state) { if(cur==n) return dp[cur][state]=1; if(dp[cur][state]!=-1) return dp[cur][state];//记忆化搜索 int ret=0; for(int i=0;i<(1<<m);i++) { if(ok(i,state,cur))//推断下一条边能否够增加 { ret+=dfs(cur+1,i); ret%=mod; } } return dp[cur][state]=ret%mod; } int main() { int t; cin>>n>>m; memset(map,0,sizeof(map)); memset(dp,-1,sizeof(dp)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>t; if(!t) map[i]|=1<<j; } } cout<<dfs(0,0)<<endl; return 0; }
相关文章
- Cocos2D实现上下滚动式状态窗口
- lxcfs 是什么? 怎样通过 lxcfs 在容器内显示容器的 CPU、内存状态
- Oracle数据库使用出现错误-状态: 失败 ORA-01034: ORACLE not available ORA-27101: shared memory realm does not exist
- GetKeyState和GetAsyncKeyState以及GetKeyboardState函数的用法与区别2-------C#检查键盘大小写锁定状态
- JAVA Eclipse开发Android如何让屏幕保持为竖直或水平状态
- codeforces B - Preparing Olympiad(dfs或者状态压缩枚举)
- HDU 3006 The Number of set(位运算 状态压缩)
- 《设计模式之禅》--备忘录扩展:多状态的备忘录
- 重新整理操作系统概念系类——进程状态与切换
- 一个好用的查看Angular应用ngrx状态的Chrome扩展:Redux devTools
- Android Recyclerview监听滑动状态
- HDU 3001 Travelling (三进制状态压缩 DP)
- 状态压缩动态规划 -- 炮兵阵地
- 【视频】React ReduxToolkit状态管理:创建store对象及redux调试工具的安装方法