poj 3254 Corn Fields (状压dp)(棋盘dp)
2024-08-31 11:33:41
状压dp入门题
因为当前行的状态只和上一行有关
所以可以一行一行来做
因为m <= 12所以可以用二进制来表示放了或者没有放
0表示没放,1表示放
f[i][state]表示第i行状态为state的方案数
f[i][state] = sum(f[i-1][state'])
枚举行,然后枚举这一行和上一行的状态
最后把最后一行所有状态的和加起来就行了
状态是这么定义,但是实际操作略有不同
因为state的状态有很多被剔除,所以我们可以只存
state数组的下标来省空间
也就是说f[i][j]表示第i行状态为state[j]的方案数
这一点貌似其他博客都没有提到。
还有几个点要注意
(1)怎么表示左右没有相邻?
这里有个骚操作 x & (x << 1)
如果这个值为真,就表示有1相邻。
这是显而易见的,不懂得拿笔画一下就知道了
可以一开始就把不可行的状态剔除,非常省时间
(2)怎么表示上下没有相邻
两行的状态取&,值为真就有相邻
(3)题目给的限制条件怎么用
题目中说0就是不可以放
那么如果是0就设为1,然后和当前状态取&
如果值为真就说明有重合,就不行
(4)最后,一个小细节
我一开始是写如果到第n - 1行(我从0开始),就更新答案。
然后是WA。
如果是单独写一个循环来更新,就AC
想了想,发现如果只有一行的话,第一种写法答案是不会被更新的。
因为如果只有一行循环根本不会进行!!!
我第一次遇到这样的坑,以后要注意
#include<cstdio>
#include<vector>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 20;
const int MAXM = 600;
const int MOD = 1e8;
int f[MAXN][MAXM], map[MAXN], n, m;
vector<int> state;
inline bool judge(int x) { return !(x & (x << 1)); }
inline bool fit(int x, int i) { return !(x & map[i]); }
void init()
{
REP(i, 0, 1 << m)
if(judge(i))
state.push_back(i);
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
memset(f, 0, sizeof(f));
state.clear(); init();
REP(i, 0, n)
{
map[i] = 0;
REP(j, 0, m)
{
int x; scanf("%d", &x);
if(x == 0) map[i] |= (1 << (m - j - 1));
}
}
REP(i, 0, state.size())
if(fit(state[i], 0))
f[0][i] = 1;
int ans = 0;
REP(i, 1, n)
REP(j, 0, state.size())
{
if(!fit(state[j], i)) continue;
REP(k, 0, state.size())
{
if(!fit(state[k], i-1)) continue;
if(state[j] & state[k]) continue;
f[i][j] = (f[i][j] + f[i-1][k]) % MOD;
}
}
_for(i, 0, state.size()) ans = (ans + f[n-1][i]) % MOD;
printf("%d\n", ans);
}
return 0;
}
最新文章
- Apache Ignite高性能分布式网格框架-初探
- Java虚拟机11:运行期优化
- [数据库操作]Java中的JDBC的使用方法.
- Jump Game | &; ||
- Android:调试之LogCat
- jvm莫名退出问题解决
- 分布式中使用Redis实现Session共享(转)
- Scala + Play + Sbt + Protractor
- Linux之yum
- Android ContentProvider详解
- Java基础--二进制运算
- 2.4配置的热更新「深入浅出ASP.NET Core系列」
- abstract、final和native几大注意点
- Redis深入学习笔记(五)Redis阻塞原因
- Unity打包提示UnityEditor.BuildPlayerWindow+BuildMethodException: Build failed with errors.错误
- python中深拷贝和浅拷贝
- 从percona server 5.7换到mariadb 10.2
- ssh-keygen 不是内部或外部命令
- [NOI1997] 积木游戏
- 在jenkins里使用SCM管理jenkinsfile
热门文章
- Linux Shell脚本编程-数组和字符串处理
- vue-cli3.0 搭建项目
- 配置监听器 服务器启动时 检索常用数据 保存在application中 减少数据的查询操作(OA项目)
- BA-风阀水阀执行器接线图
- B - Networking
- 从零開始写游戏引擎(一) - project创建以及文件夹设置还有版本号控制
- CF 558C(Amr and Chemistry-构造法)
- hadoop无法启动DataNode问题
- comp.lang.javascript FAQ [zz]
- Rose2003执行出现 -2147417848 (80010108)&;#39;:Automation 错误