关键词：
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：
就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。
附加一个关于位运算的总结：
上题干：
题目描述 Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can‘t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant. Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant. 农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。 遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。 John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案） 输入输出格式 输入格式： 第一行：两个整数M和N，用空格隔开。 第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。 输出格式： 一个整数，即牧场分配总方案数除以100,000,000的余数。 输入输出样例 输入样例#1： 复制 2 3 1 1 1 0 1 0 输出样例#1： 复制 9
题目不用多解释，直接上代码，写注释了，很好懂。
#include<cstdio> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) const int mod = 1e9; template <class T> void read(T &x) char c; bool op = 0; while(c = getchar(),c > ‘9‘ || c < ‘0‘) if(c == ‘-‘) op = 1; x = c - ‘0‘; while(c = getchar(),c <= ‘9‘&& c >= ‘0‘) x = x * 10 + c - ‘0‘; if(op == 1) x = -x; int F[15],f[15][4100],m,n,field[15][15]; int state[4110]; int main() read(m);read(n); duke(i,1,m) duke(j,1,n) read(field[i][j]); duke(i,1,m) duke(j,1,n) F[i] = (F[i] << 1) + field[i][j];//F存i行草地的情况 f[0][0] = 1; int maxn = 1 << n; duke(i,0,maxn - 1) state[i] = (((i << 1) & i) == 0) && (((i >> 1) & i) == 0); //每种状态是否可行 duke(i,1,m) duke(j,0,maxn - 1) if(state[j] && ((j & F[i]) == j)) //j是否能选 duke(k,0,maxn - 1) //上一排能选什么 if((j & k) == 0) f[i][j] = (f[i][j] + f[i - 1][k]) % mod; int ans = 0; duke(i,0,maxn - 1) ans += f[m][i]; ans %= mod; printf("%d ",ans); return 0;
状压dp入门(代码片段)
引题状压dp，全称为状态压缩动态规划，是一种利用二进制的数来表示状态的动态规划我们经常用二进制中某一位的1表示选取这一位表示的状态，用0表示相反的意义例如：现在有一张有(n)个节点的图，我们需要找到经过某些特... 查看详情
动态规划合唱队形luogu-(代码片段)
分析做两遍最长上升子序列，在遍历一下，取最大值。AC代码#include<bits/stdc++.h>usingnamespacestd;#definems(a,b)memset(a,b,sizeof(a))typedeflonglongll;inta[105];intdp1[105],dp2[105];inlineintread()intX=0,w=0;charch=0;while 查看详情
动态规划——状压树形
问题A:铺砖块时间限制: 1Sec 内存限制: 128MB题目描述现有n*m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种 输入输入n，m（1<=n,m<=11) 有多组输入数据，以m=n=0结束 ... 查看详情
信息学奥赛一本通5.4状态压缩动态规划(代码片段)
#loj10170.「一本通5.4例1」骑士看数据范围n<=10,所以不是搜索就是状压dp,又因为搜索会超时所以用dpdp[i][k][j]表示现已经放到第i行，前面共有k个，这一行状态为jso,dp[i][k][j]=dp[i-1][k-num[j]][t]#include<iostream>#include<cstdio>#include&... 查看详情
动态规划-状压dp（炮兵阵地）
P2704炮兵阵地题目描述司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H”表示），也可能是平原（用“P”表示），如下图。在每一格平原地形... 查看详情
leetcode困难132分割回文串(代码片段)
思路：动态规划用131、分割回文串的回溯思路会超时131是要记录每一种分割情况，本题只记录最小分割次数，动态规划即可。dp2[i]记录[0,i]里的最小次数classSolutionpublicintminCut(Strings)intlen=s.length();boolean[][]dp=newboole... 查看详情
[bzoj3717][pa2014]pakowanie_动态规划_状压dp
Pakowaniebzoj-3717PA-2014题目大意：给你n个物品m个包，物品有体积包有容量，问装下这些物品最少用几个包。注释：$1lenle24$，$1lemle100$想法：以为是什么超级牛逼的背包dp，结果就是状压dp状态：f[s]表示装s状态的物品需要多少背包，... 查看详情
[bzoj1879][sdoi2009]bill的挑战_动态规划_状压dp
Bill的挑战 bzoj-1879Sdoi-2009题目大意：注释：$1letle5$，$1lemle15$，$1lelengthle50$。想法：又是一个看数据范围想做法的题，我们想到状压dp。看了题解......网上给的状态是f[len][s]表示长度为len满足状态s的字符串个数。光看状态......... 查看详情
动态规划1(代码片段)
...包，依赖性问题）状态压缩，树形dp看过最好的一篇讲解动态规划的https://mp.weixin.qq.com/s/15HSidWyGg5eN--ICNNjFg微信里的一篇文章。看完之后，基本的动态规划思想就懂了，有特点的dp需要再学习，剩下的就要刷题了。/ Vijos /&nb... 查看详情
zoj2845旅游规划(代码片段)
样例333123108612120013601235010000输入13输出1332123108612120013601235010000输入2impossible输出2思路状压DP，一开始把必须要去的点压成一个数（must|=1<<(v-1);），然后预处理每个状态，s数组表示每个状态里有多少个1（走到点数），然后跑... 查看详情
动态规划_线性动态规划，区间动态规划(代码片段)
...xff1a;代码：最长公共子序列思路：代码：区间动态规划石子合并思路：代码：模板题链接：数字三角形最长递增子序列最长公共子序列石子合并线性规划数字三角形思路：状态表示ÿ 查看详情
动态规划(代码片段)
动态规划文章目录动态规划DynamicProgramming例一：fibonacci方法一：递归方法二：动态规划例二：青蛙跳台阶问题方法一：动态规划问题扩展：例三：最大连续子数组和方法：动态规划例四：字符串... 查看详情
动态规划(代码片段)
动态规划文章目录动态规划DynamicProgramming例一：fibonacci方法一：递归方法二：动态规划例二：青蛙跳台阶问题方法一：动态规划问题扩展：例三：最大连续子数组和方法：动态规划例四：字符串... 查看详情
算法动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)(代码片段)
文章目录一、动态规划简介二、自底向上的动态规划示例1、原理分析2、算法设计3、代码示例三、自顶向下的动态规划示例1、算法设计2、代码示例一、动态规划简介动态规划,英文名称DynamicProgramming,简称DP,不是具体的某种算法,... 查看详情
算法动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)(代码片段)
文章目录一、动态规划简介二、自底向上的动态规划示例1、原理分析2、算法设计3、代码示例三、自顶向下的动态规划示例1、算法设计2、代码示例一、动态规划简介动态规划,英文名称DynamicProgramming,简称DP,不是具体的某种算法,... 查看详情
《数据结构与算法之美》27——初识动态规划(代码片段)
前言今天开始学习动态规划，一共有三节，分别是：初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规划。动态规划比较适合用来求解最优问题，比如最大值、最小值等等。它可以非常显著地降低时间复... 查看详情
算法动态规划③(leetcode62.不同路径|问题分析|自顶向下的动态规划|自底向上的动态规划)(代码片段)
文章目录一、问题分析二、自顶向下的动态规划1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer5、代码示例三、自底向上的动态规划1、动态规划状态State2、动态规划初始化Initialize3、... 查看详情
算法动态规划③(leetcode62.不同路径|问题分析|自顶向下的动态规划|自底向上的动态规划)(代码片段)
文章目录一、问题分析二、自顶向下的动态规划1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer5、代码示例三、自底向上的动态规划1、动态规划状态State2、动态规划初始化Initialize3、... 查看详情