闫氏DP 学习笔记 二

书接上文：学习笔记 一

背包DP 进阶

多维费用背包

顾名思义，在背包中加入多个限制。例如每个物品都有一定的体积和质量，要求在最大体积和最大质量的限制下选出总价值最高的物品。通过加入合适的限制，这样的背包问题就会更加切合现实情况。多维费用背包的模型更贴近于生活中我们经常面临的多决策问题，因而它的求解更具有现实意义。

“多维费用”在我看来其实是一种状态设计的思想，其实并不是某种特定类型的物品取用方式，所以不宜和0/1背包等按物品取用方式区分的背包类型混为一谈。正因如此，多维费用背包问题中也会出现0/1背包、完全背包、多重背包的影子。下面的两道题目就是最好的例证：

洛谷 P1507 NASA的食物计划

题目传送门：这里

题目难度：普及-

NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

---

输入第一行 个整数，分别代表体积最大值 和质量最大值 。

输入第二行 个整数代表食品总数 。

接下来输入的 行每行 个数 体积 ，质量 ，所含卡路里 。

输出一个数，表示所能达到的最大卡路里（int 范围内）

---

数据范围：

对于 的数据，，，。

读题我们会发现，这道题设置了两个限制条件：其一为体积、其二是质量。那么该如何设计求解方案来求解呢？

运用0/1背包的思想，每个物品其实都只有“选”和“不选”两种情况。假设目前是第 个物品：如果不选，就相当于是选前 个物品的最大价值；反之就需要将背包的剩余体积和质量给更新了。我们还可以观察到，这两个限制条件是互不影响的，均分别取决于选择的物品的性质，那事情就很好办了。在dp数组里设置两个分立的维度，分别代表当前背包的剩余容量和剩余承重量，然后借助滚动数组的一点点知识就可以解决了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>

#define M 410
using namespace std;

int dp[M][M], vol[M], val[M], mas[M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int h, t, n;
	cin >> h >> t >> n;

	for (int i = 1; i <= n; i++) {
		cin >> vol[i] >> mas[i] >> val[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = t; j >= mas[i]; j--) {
			for (int k = h; k >= vol[i]; k--) {
				dp[j][k] = max(dp[j][k], dp[j - mas[i]][k - vol[i]] + val[i]);
			}
		}
	}
	cout << dp[t][h] << endl;
	return 0;
}

总用时： 记录

洛谷 P1541 乌龟棋

题目传送门：这里

题目难度：普及+/提高

题目来源：NOIp 提高组    2010

NOIP2010 提高组 T2

---

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 个格子，每个格子上一个分数（非负整数）。棋盘第 格是唯一的起点，第 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 张爬行卡片，分成 种不同的类型（ 张卡片中不一定包含所有 种类型的卡片，见样例），每种类型的卡片上分别标有 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

---

输入：

每行中两个数之间用一个空格隔开。

第 行 个正整数 ，分别表示棋盘格子数和爬行卡片数。

第 行 个非负整数，，其中 表示棋盘第 个格子上的分数。

第 行 个整数，，表示 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 张爬行卡片。

输出：

一个整数，表示小明最多能得到的分数。

---

每个测试点 1s。

对于 的数据有 ，且 种爬行卡片，每种卡片的张数不会超过 ；。

输入保证了用完所有爬行卡片后刚好到达终点，也就是说 。我们真正需要去担心的还是这 张卡片的顺序问题。

既然是多维费用背包，那我们就要找到其背后的限制条件，我们看看，每次前进某格时，什么量是变化的？

答案很明显了——卡牌的个数。我们进一步想——每种类型卡牌的个数。接下来就可以设计数组了！

考虑dp数组，状态dp[a][b][c][d]表示目前已经使用过 张四种类型的卡牌后的最大价值。在读入时进行统计，接着挨个枚举“选”和“不选”的情况即可。

那么如何确定状态转移呢？

当前所在格子的编号很显然取决于使用过的爬行卡牌的类型和数目，假设四类卡牌分别使用了 次，起始点编号为 ，那么当前格子编号就是 。

最后注意初始化，在一张卡牌都不选的情况下，也能得到第一个格子的分数！这是读题可以读出来的信息。以及下标判负（见代码）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>

#define N 45
#define M 370
#define K 130
using namespace std;

int dp[N][N][N][N], mp[M], st[K];

int getIdx(int a, int b, int c, int d) {
	// 获取下标 
	return 1 + a + b * 2 + c * 3 + d * 4;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> mp[i];
	}

	for (int i = 1; i <= m; i++) {
		// 统计每种类型卡牌的个数 
		int x;
		cin >> x;
		st[x]++;
	}

	dp[0][0][0][0] = mp[1]; // 记住初始化 

	for (int a = 0; a <= st[1]; a++) {
		for (int b = 0; b <= st[2]; b++) {
			for (int c = 0; c <= st[3]; c++) {
				for (int d = 0; d <= st[4]; d++) {
					int now = mp[getIdx(a, b, c, d)];
					 
					if (a) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a - 1][b][c][d] + now);
					if (b) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b - 1][c][d] + now);
					if (c) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c - 1][d] + now);
					if (d) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d - 1] + now);
				}
			}
		}
	}
	cout << dp[st[1]][st[2]][st[3]][st[4]] << endl;
	return 0;
}

总用时： 记录

分组背包

一般形式是——在 组中选择总重量不超过限制的、且总价值最高的一些物品，且最多在每组物品中选择其中一个计入总价值。由于这类背包描述了特定的物品选择方式，和多维费用不同，它是一种和0/1背包、完全背包、多重背包同类型的背包。

洛谷 P1757 通天之分组背包

题目传送门：这里

题目难度：普及-

自 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 背包，他的物品大致可分为 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

---

输入两个数 ，表示一共有 件物品，总重量为 。

接下来 行，每行 个数 ，表示物品的重量，利用价值，所属组数。

输出一个数，最大的利用价值。

---

数据范围：

，，， 在 int 范围内。

其实类似0/1背包的思路，因为每一组物品中至多选一个，我们就遍历某一组物品，在其中执行选或不选的判断就好。

因此我们大概需要设计三重循环——分别要枚举组数、当前组的每件物品和剩余容量。考虑到题目限制，每一组只能最多选出一件物品，因此将组数枚举放在最外层、接着是剩余价值、最后是每一组的物品。

加入“分组”的概念后，二维数组w[i][j]就代表第 组的第 个物品的价值，v 数组同理。

如果把剩余价值和每组物品枚举的顺序搞反了呢？那么输出将会是15，不难发现：程序选择了第一组的两个物品，与“每组至多选择一个物品”的要求有悖。细化到执行逻辑本身，如果每组物品的枚举放在了外边，假设当前是第 个物品，那么对于可能循环到的剩余价值 和 ，都有可能做出“选择”这一操作；接着是第 个物品，同样可能循环到剩余价值 与 ，也有可能做出“选择”这一操作，总体来说，就是这一组的第 和第 组物品都被选择了，也就造成了同一组选择超过一件物品的情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>

#define M 110
#define N 1010
using namespace std;

int w[M][N], v[M][N];
int cnt[M], dp[N];
int gr = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin>>m>>n;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		gr = max(gr, c);
		v[c][++cnt[c]] = a;
		w[c][cnt[c]] = b;
	}
	for (int i = 1; i <= gr; i++) {
		for (int k = m; k >= 0; k--) {
			for (int j = 1; j <= cnt[i]; j++) {
				if (k >= v[i][j]) dp[k] = max(dp[k], dp[k - v[i][j]] + w[i][j]);
			}
		}
	}
	cout << dp[m] << endl;
	return 0;
}

总用时： 记录

树形背包

顾名思义，树形背包是在树形结构上运行的背包算法。一般来说，树形背包所求的问题和树的边权、点权相关。

洛谷 P2015 二叉苹果树

题目传送门：这里

题目难度：普及+/提高

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 个结点（叶子点或者树枝分叉点），编号为 ，树根编号一定是 。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 个树枝的树：

1 2 3 4 5

2 5 \ / 3 4 \ / 1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

---

输入第一行有 个整数 和 ，分别表示表示树的结点数，和要保留的树枝数量。

接下来 行，每行 个整数，描述一根树枝的信息：前 个数是它连接的结点的编号，第 个数是这根树枝上苹果的数量。

输出一个数，最多能留住的苹果的数量。

---

数据范围：

，每根树枝上的苹果 。

树上背包怎么做呢？

联想一下数字三角形这道题，当时我们选择从下往上的更新方式。这道题也可以用这样的思想来解决，但是最大的一个问题是这道题的树并没有数字三角形那么规整，因此采用深搜到子节点，再向上更新的方式来更新状态。

在这道题中，我们设置dp数组为dp[u][i]，含义是以 为根，且选择了子树里 条边的方案的最大边权和。

我们把样例画成一个树状图：

样例输出 ，就是将边 和边 删去、保留节点 。

假设当前深搜到节点 ，发现无法继续向下搜索，于是开始更新边：对于边 ，可以选、也可以不选。如果不选，很简单，根据滚动数组思想，就是dp[u][i]本身；如果选择这条边，就很有意思了——

子节点不好解释，让我们向上移动一下。假设当前在 号点上DP ，对于数组第二维，可以枚举的值在 内：即一条边都不选、选子树的某一条边、子树两条边都选上。不难发现，变量的取值是 ，其中 是以节点 为根的所有子树的边数之和。

然后是前驱状态的问题，既然顺序是从下到上，那状态dp[u][j]就是从dp[son(u)][j - 1]转移来的，这里为什么是 ？因为根节点 和这个子树的根节点 中间还连了一条边，因此需要将它排除在外。循环变量 为上述数组第二维的值，用来枚举可选择的子树的边数。那么子树需要选择 条边，算上刚刚的特殊边 ，根节点 对应的树就只需要选择 条边了。最后，因为选中了边 ，因此需要累加边权，状态转移方程就是 dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[son(u)][j] + w[to[i]])

注意存无向边，因此前向星结构体数组要开 ！血的教训

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <bits/stdc++.h>

#define N 110
using namespace std;

int h[N];
int cnt[N], dp[N][N];
int idx = 0;
int n, q;

struct Edge {
    int to, ne, w;
} edges[N << 1];

void add(int u, int v, int x) {
    edges[idx].to = v;
    edges[idx].w = x;
    edges[idx].ne = h[u];
    h[u] = idx++;
}

void dfs(int now, int fa) {
    for (int i = h[now]; ~i; i = edges[i].ne) {
        int son = edges[i].to;
        if (son == fa) continue;
        dfs(son, now);
        cnt[now] += (cnt[son] + 1);
        for (int j = min(q, cnt[now]); j; j--) {
            for (int k = min(j - 1, cnt[son]); k >= 0; k--) {
                dp[now][j] = max(dp[now][j], dp[now][j - k - 1] + dp[son][k] + edges[i].w);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        add(u, v, x);
        add(v, u, x);
    }

    dfs(1, -1);

    cout << dp[1][q] << endl;

    return 0;
}

总用时： 记录

洛谷 P1352 没有上司的舞会

谨以此题，缅怀高2022届那五位被蓝桥杯官方送来的双倍经验雷倒的OIer们

题目传送门：这里

题目难度：普及+/提高

来源：福建省历届夏令营

某大学有 个职员，编号为 。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

---

输入：

第一行是一个整数 。

第 到第 行，每行一个整数，第 行的整数表示 号职员的快乐指数 。

第 到第 行，每行输入一对整数 ，代表 是 的直接上司。

输出：

输出一行一个整数代表最大的快乐指数。

---

对于 的数据，保证 $1n ^3

-128 r_i$，，且给出的关系一定是一棵树。

同样是一道经典的树形背包问题。但是和上面那个二叉苹果树不同，这道题相当于求一定条件下的点权最大和、而上一道题则是求边权最大和，因而这道题的状态表示策略稍有不同——让dp[i][0]代表员工 不来参加舞会的最大欢乐值，dp[i][1]代表员工 前来参加舞会的最大欢乐值。那么很明显，状态之间的关系就出来了。

如果这个员工不来参加，那么他的直接下属，也就是节点 直接相连的子节点，就可以自由选择来或不来，因为他的直接上司选择了不来舞会；如果这个员工参加了舞会，那么他的直接下属是无论如何也不会来的。这样就形成了一个递归的过程，看得出来父节点的状态最大值取决于子节点的“来”和“不来”状态的最大值，因此对于大boss来讲（树的根节点），只要对他“来”和“不来”两种状态取最大值即可解决问题。

整体采用深搜到子节点然后向上更新的方式，这一点和二叉苹果树相似（不用更新子树边数和），用上刚才分析的状态转移就好。值得注意的是，对每个节点的一号状态——也就是“来参加”，需要初始化成该点的欢乐值。寻根采用输入时累加节点入度的方法，如果入度为 则证明该点是树的根节点，从这里开始深搜即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>
#define N 6010
using namespace std;

typedef long long ll;

struct Edge {
	int to, ne;
} edges[N << 1];

int dp[N][2], h[N], w[N], size[N];
int indeg[N];
int idx = 0, n;

void add(int u, int v) {
	idx++;
	edges[idx].to = v;
	edges[idx].ne = h[u];
	h[u] = idx;
}

void dfs(int now, int fa) {
	for (int i = h[now]; ~i; i = edges[i].ne) {
		int son = edges[i].to;
		if (son == fa) continue;
		dfs(son, now);
		dp[now][0] += max(dp[son][0], dp[son][1]);
		dp[now][1] += dp[son][0];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	memset(h, -1, sizeof h);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		indeg[v]++;
		add(u, v);
		add(v, u);
	}
	int rt = -1;
	for (int i = 1; i <= n; i++) {
		if (!indeg[i]) {
			rt = i;
			break;
		}
	}
	for (int i = 1; i <= n; i++) dp[i][1] = w[i];
	dfs(rt, -1);
	cout << max(dp[rt][0], dp[rt][1]) << endl;
	return 0;
}

总用时： 记录

有人说数据水了，我挺赞同的……

有依赖的背包

顾名思义，有依赖的背包在选择物品时要注意主物品和副物品的从属关系。一般来说，在选择副物品前，要先把对应的主物品选择了。实质上它是一种变形的0/1背包，因此在状态转移方面和0/1背包的状态转移方程有诸多相似之处。

洛谷 P1064 金明的预算方案

题目传送门：这里

题目难度：普及+/提高

来源：NOIp 提高组    2016

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 个、 个或 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 元。于是，他把每件物品规定了一个重要度，分为 等：用整数 表示，第 等最重要。他还从因特网上查到了每件物品的价格（都是 元的整数倍）。他希望在不超过 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 件物品的价格为 ，重要度为，共选中了 件物品，编号依次为 ，则所求的总和为：

。

请你帮助金明设计一个满足要求的购物单。

---

输入第一行有两个整数，分别表示总钱数 和希望购买的物品个数 。

输入第 到第 行，每行三个整数，第 行的整数 ，， 分别表示第 件物品的价格、重要度以及它对应的的主件。如果 ，表示该物品本身是主件。

输出一行一个整数表示答案。

---

对于全部的测试点，保证 ，，，，，答案不超过 。

NOIP 2006 提高组 第二题

这道题属于是这类背包的经典入门题。不难发现，它有很明显的从属选择关系——主物品和附件。

那么在设计转移方程时就要注意，此时我们的选择方案已经不再是普通0/1背包单纯的“选”和“不选”了。而是“选哪些”和“不选”两种思考方向。

分类讨论可以发现，选择方案分五种：第一种是只选主物品、第二种是只不选主物品、第三种是选主物品且只选第一个附件、第四种是选主物品且只选第二个附件、最后一个是选主物品和所有两个附件。那么在设计转移方程时只需要分类判断 和 的大小关系，注意倒序循环！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <bits/stdc++.h>
#define N 32010
#define M 110
using namespace std;

int dp[N], w[M][3], v[M][3], cnt[M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		cnt[c]++;
		if (!c) {
			v[i][0] = a;
			w[i][0] = a * b;
		} else {
			v[c][cnt[c]] = a;
			w[c][cnt[c]] = a * b;
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= v[i][0]; j--) {
			if (!v[i][0]) break;
			dp[j] = max(dp[j], dp[j - v[i][0]] + w[i][0]);
			if (j >= (v[i][0] + v[i][1] + v[i][2])) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][1] - v[i][2]] + w[i][0] + w[i][1] + w[i][2]);
			if (j >= v[i][0] + v[i][1]) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][1]] + w[i][0] + w[i][1]);
			if (j >= v[i][0] + v[i][2]) dp[j] = max(dp[j], dp[j - v[i][0] - v[i][2]] + w[i][0] + w[i][2]);
		}
	}
	cout << dp[n] << endl;
	return 0;
}

总用时： 记录