动态规划算法刷题笔记【状压dp】-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划算法刷题笔记【状压dp】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二进制枚举子集

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++
a&1 == 1 判断是否为奇数，如果为1，则为奇数因为奇数二进制末位一定是1，所以与1 得到的结果是1

例

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

这里，1<<14——2¹⁴——第15位是1，可以表示14个1
i&（1<<j）—— 从0开始是因为，原本第1位就是1。所以j=0时，对应的就是 i 的最低位

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

状态压缩

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

旅行商问题

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

$Fl oy d$ 算法：

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

方格取数问题

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

$n o w ∣ f l a g == f l a g$ —— （1代表可以选择，0代表不可以选择）：

$10110$
$00110$
$= 10110 == f l a g$

$10110$
$01001$
$= 11111! = f l a g$

使用条件

状态需要有一定的状态单元。 即一个状态应该是保存一个集合，其中的元素值对应着0或1，例如我们常见的棋盘，我们可以用0或1来表示棋子的放置状态。而整个集合即是一个01串，即二进制数，我们通常用十进制表示。那么我们再进行状态转移或者判断的时候，需要先将十进制转化为二进制，再将二进制转化为十进制
题目中限制的集合大小不会超过20。 如果用二进制表示状态，那么集合大小为20的二进制状态有2²⁰-1，已经达到1e7的数量级了
具有动态规划的特性。 对于动态规划，一般都是要求最优化某个值，具有最优子结构的性质。同时也需要满足状态转移的特性，而不是前一个状态毫无关系的

题目

[SCOI2005] 互不侵犯

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式

只有一行，包含两个数N，K （ $1 <= N <= 9, 0 <= K <= N * N$ ）

输出格式

所得的方案数

样例输入 #1

3 2

样例输出 #1

思路

还是比较模板的一道题
国王的意思是：选定了格子，然后不能相邻（斜上方、斜下方）。跟方格取数差不多
首先对第1行进行处理，这样后面的行才能使用模板
循环模板：1. 枚举行。——2. 枚举上个阶段放了的国王数。——3. 枚举本阶段的状态。——4. 在枚举本阶段状态的同时，枚举上一阶段的状态，维护状态。

题解文章来源地址https://www.toymoban.com/news/detail-670921.html

#include<bits/stdc++.h>
using namespace std;
long long ans,n,m,k,f[10][100][1<<9+5];
int lowbit(int x){
	int tmp=0;
	while(x) tmp++,x-=x&(-x);
	return tmp;
}
int main(){
	scanf("%lld%lld",&n,&k);
	m=(1<<n)-1;
	for(int i=0;i<=m;++i){
		if(!(i&(i<<1))&&lowbit(i)<=k) 
		f[1][lowbit(i)][i]=1;
	} 
	//处理出第一行的所有情况 
	for(int i=2;i<=n;++i)//枚举行 
	for(int j=0;j<=k;++j)//枚举上个阶段放了的国王数 
	for(int x=0;x<=m;++x){//枚举本阶段的状态 
		if(x&(x<<1)) continue;//本阶段不能互相伤害 
		for(int y=0;y<=m;++y){//枚举上一个阶段的状态 
			if(x&y||x&(y<<1)||x&(y>>1)) continue;//本状态和上一个状态不能冲突
			if(j+lowbit(x)>k) continue;//本状态新放的国王数目+上个阶段国王数小于k 
			f[i][j+lowbit(x)][x]+=f[i-1][j][y];  //本状态加上一状态数 
		}
	}
	for(int j=0;j<=m;++j) ans+=f[n][k][j];
	printf("%lld",ans);
}

[NOI2001] 炮兵阵地

司令部的将军们打算在 $N\times M$ 的网格地图上部署他们的炮兵部队。

一个 $N\times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 $\texttt{H}$ 表示），也可能是平原（用 $\texttt{P}$ 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

动态规划算法刷题笔记【状压dp】,算法刷题笔记,算法,动态规划,c++

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示 $N$ 和 $M$ 。

接下来的 $N$ 行，每一行含有连续的 $M$ 个字符，按顺序表示地图中每一行的数据。

输出格式

一行一个整数，表示最多能摆放的炮兵部队的数量。

样例输入 #1

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

样例输出 #1

提示

对于 $100\%$ 的数据， $N\le 100$ ， $M\le 10$ ，保证字符仅包含 P 与 H。

思路

这道题还是有些复杂的
按照思路：1. 初始化（对第1行操作、枚举合法状态）。2. 状态转移。（循环判断后面的行是否合法——判断 i-1,i-2）

题解

#include<bits/stdc++.h>
using namespace std;
int n,m,num[60];
char s[110][15]; 
int rec[110];
int state[70],top;
int dp[110][70][70];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<(1<<m);i++){
		if((i&(i<<1)||(i&(i<<2))))continue; 
		int k=i;
		while(k){
			++num[top];
			k&=(k-1);                 //这一步是去掉k二进制下的一个1
		}
		state[top++]=i;
	}
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(int j=0;j<m;j++)
			if(s[i][j]=='H')
		 	rec[i]|=(1<<j); 
	}
	for(int i=0;i<top;i++) {
		if(state[i]&rec[0])continue;
		dp[0][0][i]=num[i];
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<top;j++) {
			if(state[j]&rec[i])continue; 
			for(int k=0;k<top;k++) {
				if(state[j]&state[k])continue;
				for(int t=0;t<top;t++) {
					if(state[j]&state[t])continue; 
					if(state[k]&state[t])continue;
					dp[i][k][j]=max(dp[i][k][j],dp[i-1][t][k]+num[j]); 
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<top;j++)
			for(int k=0;k<top;k++)
				ans=max(ans,dp[i][j][k]);
	printf("%d",ans);
}

[蓝桥杯 2019 省 A] 糖果

糖果店的老板一共有 $M$ 种口味的糖果出售。为了方便描述，我们将 $M$ 种口味编号 $1$ ∼ $M$ 。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 $K$ 颗一包整包出售。

幸好糖果包装上注明了其中 $K$ 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 $N$ 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入格式

第一行包含三个整数 $N$ 、 $M$ 和 $K$ 。

接下来 $N$ 行每行 $K$ 这整数 $T_1,T_2, \cdots ,T_K$ ，代表一包糖果的口味。

输出格式

一个整数表示答案。如果小明无法品尝所有口味，输出 $- 1$ 。

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的评测用例， $\le N \le 20$ 。

对于所有评测样例， $\le N \le 100$ ， $\le M \le 20$ ， $\le K \le 20$ ， $\le T_i \le M$ 。

蓝桥杯 2019 年省赛 A 组 I 题。

思路

看到这道题，能想到是状压dp，因为 $M, K$ 的值都挺小的，算是一种暗示吧。但是一直弄不清楚状态应该设置为什么，状态转移应该从什么样的状态转移到什么样的状态
看了别人的思路：
- 状态压缩，把每一包糖果看成一个集合，把这个集合用一个整数表示。
- 这个整数的二进制形式的第i位为1表示这包糖果里有第i种糖果
- 最多一共有2^20 = 1048576种状态
- 用已有的状态去更新加上第i包糖果后的状态

题解

#include <bits/stdc++.h>
using namespace std;
int n, m, k, x;
int a[400];
int dp[1 << 21];
int main(){
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= k; j++){ 
			cin >> x;
			a[i] |= 1 << (x - 1);     // 以二进制形式表示这包糖果中的每颗糖果
		}
	}
	memset(dp, 0x3f, sizeof(dp)); 
	dp[0] = 0; 
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < (1 << m); j++){  
			if (dp[j] > n) continue;
			dp[j | a[i]] = min(dp[j | a[i]], dp[j] + 1);
		}
	}
	if (dp[(1 << m) - 1] > n) cout << -1;   
	else cout << dp[(1 << m) - 1];       
}

[蓝桥杯 2022 省 B] 李白打酒加强版

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 $2$ 斗。他边走边唱：

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 $N$ 次，遇到花 $M$ 次。已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能?

注意：壶里没酒（ $0$ 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 $1000000007$ （即 $10^9+7$ ）的结果。

样例输入 #1

5 10

样例输出 #1

提示

【样例说明】

如果我们用 0 代表遇到花，1 代表遇到店， $14$ 种顺序如下:

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

【评测用例规模与约定】

对于 $\%$ 的评测用例： $\leq N, M \leq 10$ 。

对于 $\%$ 的评测用例： $\leq N, M \leq 100$ 。

蓝桥杯 2022 省赛 B 组 I 题。

思路

思路就像经典的李白打酒一样，状压，然后枚举相应状态是否符合条件。但是，这样最多就只能过40%数据，因为要开 $2^{n+m}$ ，按照传统的方法来，肯定MLE
看了别人的思路：不用状态压缩，因为没办法压缩
- 首先我们有必要对酒的奇偶性进行讨论，因为当走到第i个位置时酒的数量为奇，则第i个位置不可能为店，因为无论是奇数还是偶数，乘以2得到的数都是一个偶数，所以只有当k是偶数时第i个位置才可能是店
- 假如第i个位置是店，那么这个时候在第i-1个位置的酒的数量就是k/2，而遇到花的数量跟第i-1个位置是一样的都是j，这个很好理解
- 下面再看一下第i个位置是花的情况，那么第i-1个位置的酒的数量一定是k+1，因为在第i个位置消耗了1，而到达第i个位置遇到的花的数量就要比第i-1个位置遇到花的数量多1，因为我们现在是在假设第i个位置是花

题解

#include<bits/stdc++.h>
using namespace std;
const int N=113;
const int mod=1e9+7;
long long f[N*2][N][N];//f[i][j][k]表示走到了第i个位置，遇到了j个花，还剩 k斗酒的合法方案数 
int main(){
	f[0][0][2]=1;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n+m;i++)
	for(int j=0;j<m;j++)
	for(int k=0;k<=m;k++)//酒的数量不能超过花的数量，否则就算之后一直是花也喝不完 
	{
		if(!(k&1))//k是偶数，则第i个位置可以是店，否则不可以是店
			f[i][j][k]=(f[i][j][k]+f[i-1][j][k>>1])%mod;
		if(j>=1)//无论k是奇数还是偶数，第i个位置都可以是花 
			f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
	}
	printf("%lld",f[n+m-1][m-1][1]);
}