锐客网

  1. 首页 > it技术 > >

C算法|DP状态压缩之棋盘问题

写在前面 状态压缩的思想是将难以用机器语言表达具象的现实实物进行抽象.常常用二进制数来表达一种状态比方说有A、B、C，三个方案，2=010表示不选A，选B，不选C的方案，于是要枚举所有方案只需要枚举0-1< P.A 玉米地题目链接 农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。
非常遗憾，部分土地是不育的，无法种植。
而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第 1 行包含两个整数 M 和 N。
第 2…M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。
输出格式
输出总种植方法对 108 取模后的值。
数据范围
1≤M,N≤12
输入样例：
2 3
1 1 1
0 1 0
输出样例：在这里插入代码片
9
算法分析
题目的主要限制有两个方面，一个是土壤可能不能种植，而是玉米直接的相邻情况。
我们尝试用二进制来表达没一行的玉米种植情况。0代表不种，1代表种，考虑同一行的情况，该二进制数不能有相邻的两个1，考虑上一行的情况，每一位的对应位置自然也不能有相邻的1。
与前言类似，我们用0-1< 假设没有土地限制对于每个方案我们进行筛选
1.相邻两位上不含1的数为一行合法状态

bool check(int x) {return !(x&x>>1); }

2.对于每一行合法状态，对其拓展下一行合法即为判断上下两行是否有1
for(int i=0; i.size(); i++) for(int j=0; j.size(); j++) {int a=state[i],b=state[j]; if((a&b)==0) h[i].push_back(j); }

3.判断与地图情况是否符合即土地为0的地方，这一位方案为1
if((g[i]&state[j])==0) {for(auto k:h[j]) {f[i][j]=(f[i][j]+f[i-1][k])%mod; } }

4.状态表达用f[i][j]，表示已经排完i行且第i行状态为j的方案数很自然的得到状态转移方程
for(auto k:h[j]) {f[i][j]=(f[i][j]+f[i-1][k])%mod; }

ACcode
#include using namespace std; int n,m; const int N=1<<12,mod=1e8; int g[15],f[15][N]; vectorstate; //相邻位不含1的方案 vectorh[N]; //h[i]储存所有状态i可以变化的合理方案j bool check(int x) {return !(x&x>>1); //O（1）判断一个数是否有两个相邻1 } int main() {cin>>n>>m; for(int i=1; i<=n; i++) for(int j=0; j>t; g[i]+=!t*(1<

PB 小国王题目链接 在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
输入格式
共一行，包含两个整数 n 和 k。
【C算法|DP状态压缩之棋盘问题】输出格式
共一行，表示方案总数，若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
输入样例：
3 2
输出样例：
16
算法分析 与上一题类似，限制条件少了地图限制，多了每行之间的限制我们将上下行的合理转移修改为
for(int i=0; i.size(); i++) for(int j=0; j.size(); j++) {int a=state[i],b=state[j]; if((a&b)==0&&(check(a|b))) {head[i].push_back(j); } }

状态表示
这题多了个限制是k个国王，于是将状态多开一维见代码注释
ACcode
#include using namespace std; const int N=1<<10; long long f[12][110][N]; //第一维代表第i行，第二维代表已经有j个国王，第三维代表方案状态 vectorstate; vectorhead[N]; int cnt[N]; int n,k; void count(int x)//计算每个二进制数中1的个数 {for(int i=0; i>i&1)cnt[x]++; } bool check(int x) {return !(x&x>>1); } int main() {cin>>n>>k; for(int i=0; i<1<=c)f[i][j][a]+=f[i-1][j-c][b]; } cout<

    推荐阅读


    上一篇：计算机毕业设计|基于Android平台的酒店预订管理系统软件设计的论文

    下一篇：Pytorch深度学习|Pytorch深度学习实践（b站刘二大人）_03讲（梯度下降）