2024.1.31 DP动态规划习题
|
18,605
|
0
|
动态规划,集训

4400 字
|
28 分钟

A – Frog 2

题目：

Problem Statement

现有 N 个石头，分别标记为 1, 2, …, N。对于每一个石头 i (1 ≤ i ≤ N)有一个高度记为 hi。

现有一只青蛙在石头 1 上，它想通过一些跳跃到达石头 N：

  • 如果青蛙此时在石头 i 上，那么它可以跳到石头 i + 1， 石头 i + 2， … ，石头 i + K 中的某一个上。这次跳跃需要消耗它 |hi – hj| 能量，其中 j 为青蛙跳跃到达的石头序号。

找到青蛙到达石头 N 消耗能量可能的最小值。

Constraints

  • 输入的所有值均为整数。
  • 2 ≤ N ≤ 105
  • 1 ≤ K ≤ 100
  • 1 ≤ hi ≤ 104

Input

标准输入格式如下：N K
h1 h2 … hN

Output

输出青蛙消耗能量可能的最小值。

NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

这道题如果用搜索去做的话，一个是数据量太大，DFS很可能会爆栈，并且也会因为层数太多，导致BFS过慢，另一方面是搜索的空间是不确定的，因为有个k在影响，所以搜索会特别难写。所以用递推的话，就能以较快的时间结束。我们可以以搜索的思路去想这个状态转移，比如我们假设第 i 个石头处青蛙的最低能耗是 dp[ i ] ，那我们就会去搜索 dp[ i – 1 ] …… dp[ i – k ]，我们就可以说，dp[ i ] 的值是从 dp[ i – 1 ] …… dp[ i – k ] 转移而来的。

根据题意可以写出递推式：

$$ dp[i] = dp[i – 1] + |h_i – h_{i – 1}| \quad \text{或者} \quad dp[i] = dp[i – 2] + |h_i – h_{i – 2}| \quad \text{等等等……} $$

我们可以总结出一个转移式就是：

$$ dp[i] = \min(dp[j] + |h_i – h_j|) \quad (1 \leq j < i) $$

然后按照这个思路去写就好了，注意不要数组越界！

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int h[MAXN];
int dp[MAXN];
int main(){
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		cin >> h[i];
	}
	//考虑转移状态,dp[i] = min(dp[j] + |hi - hj|)
	memset(dp,0x3f,sizeof(dp));
	dp[1] = 0;
	for(int i = 2;i <= n;i++){
		for(int j = max(1,i - k);j < i;j++){
			dp[i] = min(dp[i],dp[j] + abs(h[i] - h[j]));
		}
	}
	cout << dp[n] << "\n";
}

B – Vacation

题目：

问题描述

假设小李在接下来的$n$天里只能玩三种游戏之一，即在第$i$天$(1 \leq i \leq n)$，他可能会玩：

  1. 大农特农，并获得$a_i$点快乐值。
  2. 大原特原，并获得$b_i$点快乐值。
  3. 大轨特轨，并获得$c_i$点快乐值。

但小李不会连续玩同一种游戏两天及以上。现在需要求出小李在$n$天后能获得的最大快乐值。

输入格式

输入第一行包含一个整数$n$，表示天数。

接下来$n$行，每行包含3个整数，分别表示$a_i$，$b_i$，$c_i$。

数据范围

$1 \leq n \leq 10^5$

$1 \leq a_i, b_i, c_i \leq 10^4$

输出格式

输出包含一个整数，表示答案。

NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

对于这种大数据量的题目，都几乎不考虑搜索，而是考虑DP。

我们会发现这道题和上一题不同的地方在于，这道题的状态很多。我们每天可以选择第一种第二种第三种，不同的决策又会有不同的快乐值。我们可以先假定第 i 天我们选择了第一种，那此时 dp[ i ] = max（上一天选择第二种，上一天选择第三种） + a[ i ]；假定第 i 天我们选择了第二种，那此时 dp[ i ] = max（上一天选择第一种，上一天选择第三种） + b[ i ]；假定第 i 天我们选择了第三种，那此时 dp[ i ] = max（上一天选择第一种，上一天选择第二种） + c[ i ]。

此时我们可以写出三种递推式：

$dp_1[i]=max(dp_2[i – 1],dp_2[i – 1])+a[i]$

$dp_2[i]=max(dp_1[i – 1],dp_3[i – 1])+b[i]$

$dp_3[i]=max(dp_1[i – 1],dp_2[i – 1])+c[i]$

最后我们三种取max就行。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int dp1[MAXN];
int dp2[MAXN];
int dp3[MAXN];
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	for(int i = 1;i <= n;i++){
		dp1[i] = max(dp2[i - 1],dp3[i - 1]) + a[i];
		dp2[i] = max(dp1[i - 1],dp3[i - 1]) + b[i];
		dp3[i] = max(dp1[i - 1],dp2[i - 1]) + c[i];
	}
	cout << max(max(dp1[n],dp2[n]),dp3[n]) << "\n";
}

C – Knapsack 2

题目：

Problem Statement

Peter现有 N 个物品，序号分别为 1, 2, … , N。对于每个 i (1 ≤ i ≤ N)，物品 i 有一个体积 wi 和一个价值 vi。

Peter想在这 N 个物品中选取一些放到大背包里带回家。已知背包的容积为 W，这意味着所带物品的总体积不能超过 W。

求出Peter可以带回家的物品总价值可能的最大值。

Constraints

  • 输入的所有数值均为整数。
  • $1 ≤ N ≤ 100$
  • $1 ≤ W ≤ 10^9$
  • $1 ≤ wi ≤ W$
  • $1 ≤ vi ≤ 10^3$

Input

标准输入格式如下：N W
w1 v1
w2 v2
:
wN vN

Output

输出Peter可以带回家的物品总价值可能的最大值。

NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

这就是很经典的背包DP。我们像搜索一样来思考这么两个问题：怎么定义背包的状态，怎么定义转移。

首先，怎么定义背包的状态，我们就来思考有哪些数据需要被记录：背包中物品的价值、背包中物品的重量。

所以我们可以开个一维数组处理这件事：假设用dp [ i ] 表示【背包中物品的价值】，用 i 表示【背包中物品的重量】。

所以我们假设此时物品的总重量是 i ,下一个放进来的物品的下标是 j ,就得到：

$\text{dp}[i + w_j] = \text{dp}[i] + v_j$

然后我们也不知道 i 和 j 是谁，把 j 从1 到 n 枚举一下，把 i 从 0 到 $W – W[j]$ (能让物品 j 进来的空间），最后取max值就好。

但是要注意一点，因为放进来的物品会影响到之后的判断，即我们会把物品 j 多次放入背包。

这是为什么，因为我们求 $dp[ i + w_j]$ 的状态的时候，是依据 $dp[i]$ 的状态再加上 j 物品的价值

但是我们不知道dp[i]里面是否已经包含 j 物品了，因为 j 每次都从 1 开始枚举到 n (即所有物品)

所以我们应该反向枚举 i ，即从W枚举到$W_j$，转换式变为 $\text{dp}[i] = \text{dp}[i – w_j] + v_j$ ，此时前面较小的 $dp[i]$ 就不会影响到后面较大的 $dp[ i ]$ ，因为我们底层的思想没有变，所以是可以理解的。

但是！对于这道题目！

这个时候我们来看这个数据范围：

  • $1 ≤ N ≤ 100$
  • $1 ≤ W ≤ 10^9$
  • $1 ≤ wi ≤ W$
  • $1 ≤ vi ≤ 10^3$

我们可以看到，W的数据范围高达1e9，根本没办法开数组做，所以我们得换换思路。我们可以看到V的数据范围小，我们可以反过来做处理，用 dp [ i ] 表示【背包中物品的重量】，用 i 表示【背包中物品的价值】。最后遍历一遍dp数组，就可以找到最大的有效 i 了，此时 i 的范围在1e5左右，是可以实现的。

重新思考一下转移，我们假设此时物品的总价值是 i ,上一个放进来的物品的下标是 j ，

就得到： $dp[i] = dp[i – v_j] + w[j]$ ,我们依然暴力枚举 i 和 j 就行，并且依然遵循之前说的 i 要反向遍历，从 最大可能的价值100000遍历到 $vv[ j ]$ 。

注意！我们此时的 dp[ i ] 代表的是重量，而不是价值，所以我们要的是不大于W的最大价值，每次要取的是min。所以先把dp数组设为无穷大即可。但是 dp[0] 要设为 0 ，否则会影响递推的结果。

代码 0-1背包：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 7;
int dp[MAXN];
int ww[MAXN];
int vv[MAXN];

int main(){
	int n,w;
	cin >> n >> w;
	for(int i = 1;i <= n;i++){
		cin >> ww[i] >> vv[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = w;j >= ww[i];j--){
			dp[j] = max(dp[j - ww[i]] + vv[i],dp[j]);
		}
	}

	cout << dp[n] << "\n";
}

代码（AC)：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int dp[MAXN];
int ww[MAXN];
int vv[MAXN];

int main(){
	int n,w;
	cin >> n >> w;
	memset(dp,0x3f,sizeof(dp));
	dp[0] = 0;
	for(int i = 1;i <= n;i++){
		cin >> ww[i] >> vv[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = 100000;j >= vv[i];j--){
			dp[j] = min(dp[j],dp[j - vv[i]] + ww[i]);
		}
	}
	for(int i = 100000;i >= 0;i--){
		if(dp[i] <= w){
			cout << i << "\n";
			break;
		}
	}
}

D – LCS

题目：

Problem Statement

给定字符串 s 和 t。找到一个最长的字符串，它是 s 和 t 的子序列。

Notes

字符串 x 的子序列是通过在不更改顺序的情况下从 x 中删除零个或多个字符并连接其余字符而获得的字符串。

Constraints

s 和 t 是由小写英文字母组成的字符串。

$1 \leq |s|, |t| \leq 3000$

Input

输入从标准输入中按以下格式给出：

$s$
$t$

Output

打印一个最长的字符串，该字符串是 s 和 t 的子序列。如果有多个这样的字符串，则其中任何一个都将被接受。

NENU寒假DP练习 – Virtual Judge — NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

来思考一下这种题目的思路应该是什么。给你两个字符串，去找最长的公共子序列。先思考，我们应该怎么定义状态和转移。

我们需要记录的状态有哪些东西？我们需要记录我们遍历到两个字符串的哪个位置，此时具有的字符串又是多长的，又是哪些字符。

所以我们可以开个二维数组 $dp[ i ][ j ]$ ，用 i 和 j 记录遍历到的位置，dp的值表示字符串长度，再开一个字符串变量存储最长的结果。

我们来思考一下转移的过程。假设我们此时遍历到 字符串a的 第 i 位 和 字符串b的 第 j 位，即 $dp[ i ][ j ]$

假设此时 a[i] == b[j]，那就说明我们的最长公共子序列可在之前的基础上+1，所以 $dp[ i ][ j ] = dp[i – 1][j – 1] + 1$

反之，我们的公共子序列的长度就没有变化，$dp[i][j]$ 的值就和 $max(dp[i][j – 1],dp[i – 1][j])$ 是一样的。

我们通过回溯动态规划数组 dp，便能构建最长公共子序列的字符串 str。

回溯的过程是这样的：

  • 如果 s[i – 1] 等于 t[j – 1]，说明当前字符是最长公共子序列的一部分，将该字符加入到结果字符串 str 中，并同时将 i 和 j 向前移动一个位置。
  • 如果 s[i – 1] 不等于 t[j – 1]，根据动态规划数组 dp 的值，决定怎么向左移动。如果 $dp[i – 1][j] < dp[i][j – 1]$，意味着向左移动 j 的值更有可能使得最长公共子序列变长，即 j– 。如果 $dp[i – 1][j] >= dp[i][j – 1]$，意味着向左移动 i 的值更有可能使得最长公共子序列变长，即 i–。

最后逆序输出字符串 str ，即可得到结果。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 7;
int dp[MAXN][MAXN];

int main(){
	string s,t;
	cin >> s >> t;
	int len1 = s.size();
	int len2 = t.size();
	for(int i = 1;i <= len1;i++){
		for(int j = 1;j <= len2;j++){
			if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
		}
	}
	string str = "";
	int i = len1,j = len2;
	while(i != 0 && j != 0){
		if(s[i - 1] == t[j - 1]){
			str += s[i - 1];
			i--;
			j--;
		}else{
			dp[i - 1][j] < dp[i][j - 1] ? j--:i--;
		}
	}
	for(int i = str.size() - 1;i >= 0;i--)
		cout << str[i];
	cout << "\n";
}

E – Grid 1

题目：

Problem Statement

有一个网格，其中有 H 个水平行和 W 个垂直列。用 $(i,j)$ 表示从顶部第 i 行和从左侧第 j 列的方块。

对于每个 i 和 j $(1 \leq i \leq H, 1 \leq j \leq W)$，方块 $(i,j)$ 由字符 $a_{i,j}$ 描述。如果 $a_{i,j}$ 是.，则方块 $(i,j)$ 是一个空方块；如果 $a_{i,j}$ 是#，则方块 $(i,j)$ 是一个墙方块。保证方块 $(1,1)$ 和 $(H,W)$ 是空方块。

Taro 将从方块 $(1,1)$ 开始，通过重复向右或向下移动到相邻的空方块，到达 $(H,W)$。

找到从方块 $(1,1)$ 到 $(H,W)$ 的 Taro 路径数量。由于答案可能非常大，找到对 $10^9 + 7$ 取模的计数。

Constraints

H 和 W 为整数。 $2 \leq H, W \leq 1000$ $a_{i,j}$ 为.或#。 方块 $(1,1)$ 和 $(H,W)$ 是空方块。

Input

输入以以下格式从标准输入给出：

$H \space W$

$a_{1,1} \ldots a_{1,W}$

$\vdots$

$a_{H,1} \ldots a_{H,W}$

Output

打印从方块 $(1,1)$ 到 $(H,W)$ 的 Taro 路径数量，对 $10^9 + 7$ 取模。

NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

我们还是思考这两个事情：状态和转移。

状态就是我们要记录路径的个数。

转移的话，每个格子可以从左边和上面的格子转移下来。

所以我们开个二维dp数组，用来存储从起点到达（i，j）处的路径个数。初始化起点$dp[1][1] = 1$，遇到墙肯定是没有路径的，所以墙就是0。最后输出$dp[h][w]$的值就行。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 7;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN];
char mx[MAXN][MAXN];

int main(){
	int h,w;
	cin >> h >> w;
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			cin >> mx[i][j];
		}
	}
	dp[1][1] = 1;
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if(mx[i][j] == '#'){
				dp[i][j] = 0;
				continue;
			}
			if(i > 1){
				dp[i][j] += dp[i - 1][j];
				dp[i][j] %= MOD;
			}
			if(j > 1){
				dp[i][j] += dp[i][j - 1];
				dp[i][j] %= MOD;
			}
		}
	}
	cout << dp[h][w] << "\n";
}

F – Matching

题目：

Problem Statement

有N个男人和N个女人，分别编号为1,2,…,N。

对于每对i,j$（1 \leq i,j \leq N）$，男人i和女人j的相容性以整数$a_{i,j}$给出。如果$a_{i,j}=1$，则男人i和女人j是相容的；如果$a_{i,j}=0$，则他们不相容。

Taro 试图组成N对，每对由一个男人和一个女人组成，他们之间是相容的。在这里，每个男人和每个女人必须属于恰好一个配对。

找出 Taro 可以组成N对的方式数，取模$10^9+7$。

Constraints

  • 输入中的所有值均为整数。
  • $1 \leq N \leq 21$
  • $a_{i,j}$为0或1。

Input

输入以以下格式从标准输入给出：

N

$a_{1,1} a_{1,2} … a_{1,N}$

$… $

$a_{N,1} a_{N,2} … a_{N,N}$

Output

输出 Taro 可以组成N对的方式数，取模$10^9+7$。

NENU寒假DP练习 – Virtual Judge (vjudge.net)

思路：

我们还是思考怎么定义状态还有转移。

我们要记录的状态有哪些信息呢？我们会发现这道题目，我们连状态都很难定义，因为我们没办法通过第 i 个男人和第 j 个女人这种方式，就把一种状态定义下来。

我们考虑一种新的角度，我们把所有女生看作一个集合，集合里每个女生有匹配和没匹配两种状态，所以这个集合的大小为$2^n$

然后我们用 $dp_{i,s}$ 表示前 i 个男生和S中女生匹配的方案数。

则可得到状态转移：$dp_{i,S} = \sum{dp_{i-1,S-j},j \in S \ \text{and} \ g[i][j]=1}$ ，即由前 i – 1个男生和 { S – j } 个女生 的状态转移而来，此时第 i 个男生要和选中的第 j 个女生匹配，前 i – 1 个男生不能和第 j 个女生匹配。如果我们开个21维的 $dp[2][2]…[2]$ 也太麻烦了，所以我们可以开个数组 $dp[1 << n]$ 。

这就是状压DP，当看到 $1 \leq N \leq 21$ 的时候，其实就可以往状压的角度思考，因为 $2^n$ 不是很大。

代码和注释已经尽量讲明白了，看代码理解吧。

因为 $dp[i][s]$ 只和 $dp[i – 1][s – j]$ 有关，所以也可以降维成一维的处理，这个优化交给读者。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 25;
const int MOD = 1e9 + 7;
int dp[22][4194304];//dp[i][j]表示枚举到第j个状态时，前i个男生都有匹配的方案数
int a[MAXN][MAXN];
int count(int n){
	int cnt = 0;
	while(n){
		if(n & 1){
			cnt++;
		}
		n = n >> 1;
	}
	return cnt;
}
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			cin >> a[i][j];
		}
	}
	//表示女生匹配的状态
	int m = 1 << n;
	//没有人相互匹配的方案有1种
	dp[0][0] = 1;
	//枚举前 i 个男生匹配 k 个女生的方案数
	for(int i = 1;i <= n;i++){
		//枚举所有的匹配状态，此时状态j表示有i对被匹配
		for(int j = 0;j < m;j++){
			//假设这个匹配状态和前 i 个男生已经匹配这件事不符合就跳过
			if(count(j) != i){
				continue;
			}
			//此时枚举到的S集合状态代表已经有 i 对了
			//此时枚举该状态的所有匹配的女生，必须是男女相容且应当要被匹配的
			for(int k = 1;k <= n;k++){
				//要第 i 个男生和第 k 个女生相容，并且第 k 个女生是我们选中准备匹配的
				if(a[i][k] && (j >> (k - 1) & 1)){
					//更新dp[i][j]的值，加上前 i-1 个男生和第 k 个女生未匹配的状态数
					//前 i-1 个男生和第 k 个女生未匹配的状态数用当前枚举到的状态j - (1 << (k - 1)）表示
					//这里的(1 << (k - 1)）表示状态表里，第k位女生为匹配的状态
					//j - (1 << (k - 1))是将当前匹配状态j中去掉第k个女生的匹配状态
					dp[i][j] = (dp[i][j] + dp[i - 1][j - (1 << (k - 1))]) % MOD;
				}
			}
		}
	}
	//输出前n个男生对于m种状态的匹配数
	cout << dp[n][m - 1] << "\n";
}

总结

这套题难度适中，最后一题状压比较难整，但前几题几乎都是变形题，较有教学意义。

  1. 线性DP较为简单，考虑思路就是“定义状态”+“定义转移”，可以先考虑用搜索的思路去做
  2. 无论是DP还是搜索问题，我们都要注意数据范围！！！数据范围甚至能给你一些解题思路
  3. DP无板题，学会了基本思想之后，多做题收集经验很重要
  4. 状态压缩的思想也挺重要，可以收集起来
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇