NOIP训练营集训笔记-动态规划Part2（上）路径行走问题
点击一下标题可查看其他相关笔记！
温馨提示：大家好，由于OI交流群（群号283478320）进群人数众多，容纳人数有限，目前3000人已满，如果1群满员的情况下，我们已经开通OI交流群2群（群号：549859236），供大家交流使用。有兴趣的同学和家长也可以到2群交流分享，把经验和知识分享给更多的同学。我们会选择一些活跃的同学或家长作为2群的管理员。谢谢大家~
NOIP训练营笔记
状态压缩DP：
* 状态压缩 DP：利用位运算来记录状态，并实现动态规划。
* 问题特点：数据规模较小；不能使用简单的算法解决。
* 给定两个布尔变量a,b，他们之间可进行布尔运算：
* 与运算 and：当 a,b 均为真的时候， a 与 b为真；
* 或运算 or：当 a,b 均为假的时候， a 或 b为假；
* 非运算 not：当 a 均为真的时候， 非 a为假；
* 异或运算 xor：当 a,b 不是同时真，或者同时假的时候， a 异或 b为真。
* 我们把 0 视作布尔的假，1 视作布尔的真，则整数亦存在二进制的运算，而运算的结果则是二进制里对应的位作相应的布尔操作。（按位运算）
* (23)10 = (10111)2,(10)10 = (1010)2；
* 与运算 and： 23 and 10 = (10)2 = 2
* 或运算 or： 23 or 10 = (11111)2 = 31
* 异或运算 xor： 23 xor 10 = (11101)2 = 29
* 另外，在整数位运算中还有位移操作：
* (23)10 = (10111)2,(10)10 = (1010)2；
* 左移 «：将整个二进制向左移动若干位，并用 0 补充；
- 10 << 1 = (10100)2 = 20（左移n位=乘以2n）
* 右移 »：将整个二进制向右移动若干位(实际最右边的几位就消失了)；
- 23 >> 2 = (101)2 = 5（右移n位=除以2n）
位运算比加减乘除都快！
经典例题：玉米田（Luogu 1879）
农场主 John 新买了一块长方形的新牧场，这块牧场被划分成 M 行 N列 (1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。 John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
- 1 1 1
- 0 1 0 (1 代表这块土地适合种草)
- 总方案数： 9
* 问题限制：没有哪两块草地有公共边
* 考虑动态规划：如何划分状态？
- 从上到下，从左到右？
- 记录 F[i][j] 为 (i,j) 选择在这个位置种草的方案数？
- 问题：如何转移？我们只能限制左边的位置不能种草；不能限制上面的位置不能种草，所以这样不可行！
* 划分状态：考虑用行来划分状态； 第 i 行的状态只取决于第 i-1 行。
* 状态表示：如何表示一行的种草状态？
* 二进制位：将一整行看作是一个大的二进制数，其上为 1 表示种了草， 0表示没有种草，最好不用二维数组，因为行列数目不定，不好开数组。
* 这样，我们可以用一个数来表示一行的种草状态；
例如：下图中，在一行的第一个位置和第四个位置种草，可以用18来表示这种状态：
* 状态设计：设 F[i][j] 为已经处理到第 i 行，且第 i 行的状态是 j，的总方案数。 (其中 j 为一个大的二进制数)
* 状态转移：枚举前一行的种草状态 k，如果没有产生冲突，则加上：
F[i][j] = ∑ F[i − 1][k]
* 问题：如何判断两个状态是否冲突？ 如何运用二进制运算？
* 解决方案：采取与运算；如果两个状态是冲突的，则肯定有一位上都为1， and 的结果肯定不为 0；否则若结果为 0，则代表状态不冲突。
* 下一个问题：如何判断当前状态j是合法的？
1 没有占有障碍物：和判断两个状态是否冲突是类似的。
2 左右位置判断：与上一行判断冲突，我们只考虑到了上下位置不可能同时种草，但还没有考虑左右的情况。
- 解决方案： j & (j«1) = 0 且 j & (j»1) = 0（我只想说：左右两个相互叠加判断，真TM聪明！）
//T31:玉米田（状态压缩DP）
const int N=13;//边长
const int S=(1<<N)+5;//二进制状态数=213，+5的目的是让心里有个安慰~应该不会爆炸吧O(∩_∩)O，开大点数组这样
int a[N][N];//棋盘数组
int s[N];//每一行空地的状态
int f[N][S];//动态规划数组
int g[S];//标记一个状态是否合法
//主过程
ts=1<<m;//总状态数
for(int i=0;i<ts;++i)//判断左右位置
g[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);//左右位置是否有冲突
//T31:玉米田（状态压缩DP）
f[0][0]=1;//初值！
for(int i=1;i<=n;++i)//枚举行
for(int j=0;j<ts;++j)//枚举这行的状态
if(g[j]&&((j&s[i])==j))//状态本身合法且不占障碍物
{
for(int k=0;k<ts;++k)//枚举上一行的状态
if((k&j)==0)//如果不冲突
f[i][j]=(f[i][j]+f[i-1][k])%MOD;
}
int ans=0;
for(int j=0;j<ts;++j)
ans=(ans+f[n][j])%MOD;//答案加起来
//T31:玉米田（状态压缩DP）
cin>>n>>m;//读入棋盘状态
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>a[i][j];
for(int i=1;i<=n;++i)//预处理每一行的状态
for(int j=1;j<=m;++j)
s[i]=(s[i]<<1)+a[i][j];
经典例题：互不侵犯（Luogu 1896）
* 在 N×N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。
- 3 2 (在 3×3 的棋盘内放置 2 个国王)
- 总方案数： 16
* 状态设计：设 F[i][j][k] 为已经处理到第 i 行，且第 i 行的状态是j，现在一共放置了 k 个国王的总方案数。 (其中 j 为一个大的二进制数)
* 状态转移：枚举前一行的放置国王状态为 l，如果没有产生冲突，则加上(其中 x 为状态 j 的国王数)
F[i][j][k] = ∑ F[i − 1][l][k − x]
* 问题：如何判断两个状态是否冲突？ 如何运用二进制运算？
//T32:互不侵犯（状态压缩DP）
const int N=10;
const int S=(1<<N)+5;//二进制状态数
int cnt[S];//记录一个状态有多少个1（按照这个状态放国王，一共有多少个国王）
int g[S];//记录一个状态是否合法
int h[S];
LL f[N][S][N*N];//动态转移状态->[行][状态][一共摆了多少个国王]
//T32:互不侵犯（状态压缩DP）
ts=1<<n;
for(int i=0;i<ts;++i)
{
g[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);
h[i]=i|(i<<1)|(i>>1);//h：一个状态把它左右都占据之后的状态（h[i]表示第i个国王把他左右旁边占领之后，标记为1）
cnt[i]=cnt[i>>1]+(i&1);//计算多少个1（(i&1)表示最后一个是1就++）
}
//T32:互不侵犯（状态压缩DP）
f[0][0][0]=1;//初值
//顺推
for(int i=0;i<n;++i)//行数
for(int j=0;j<ts;++j)//这一行状态
for(int l=0;l<=k;++l) if(f[i][j][l])//枚举个数
for(int p=0;p<ts;++p)//枚举下一行
if(g[p]&&((h[p]&j)==0))//如果是合法状态，且不冲突（p是一个合法状态，p国王占的领地和j是没有冲突的）
{
f[i+1][p][l+cnt[p]]+=f[i][j][l];
}
LL ans=0;//答案
for(int j=0;j<ts;++j) ans+=f[n][j][k];//所有的状态都能成为答案
联系客服
