动态规划中得到具体决策方案
动态规划中通过记录选择路径或逆推状态，实现最优解对应的具体决策方案恢复。
动态规划中得到具体决策方案
动态规划中得到具体决策方案
最长公共子序列
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
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 最大字符串长度
const int MAXN = 5001;
// dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度
vector<vector<int>> dp(MAXN, vector<int>(MAXN));
// 存放最终的最长公共子序列字符数组
vector<char> path(MAXN);
string s1, s2;
// n: s1 长度，m: s2 长度，k: 最长公共子序列长度
int n, m, k;
void computeDp() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1]) {
// 如果当前字符匹配，最长公共子序列在 i-1, j-1 的基础上加 1
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// 否则取左边或上边较大的值
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
}
// 逆推恢复一条最长公共子序列路径（不一定是唯一）
void lcs() {
computeDp();
k = dp[n][m]; // 最终的最长公共子序列长度保存在 dp[n][m]
if (k <= 0) return;
int len = k;
int i = n, j = m;
// 从 dp[n][m] 逆推回去构造子序列
while (len > 0) {
if (s1[i - 1] == s2[j - 1]) {
// 如果当前字符匹配，放入结果中，并向左上角移动
path[--len] = s1[i - 1];
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
// 向上走
i--;
} else {
// 向左走
j--;
}
}
}
int main() {
cin >> s1 >> s2;
n = s1.length();
m = s2.length();
lcs();
if (k == 0) {
cout << -1 << '\n';
} else {
for (int i = 0; i < k; ++i)
cout << path[i];
cout << '\n';
}
return 0;
}
1125. 最小的必要团队
- 状压 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <climits>
using namespace std;
class Solution {
public:
// 主函数：返回最小必要团队
vector<int> smallestSufficientTeam(vector<string> &skills, vector<vector<string>> &people) {
int n = skills.size(); // 技能总数
int m = people.size(); // 候选人数
unordered_map<string, int> skillToBit;
// 为每个必要技能分配一个唯一编号
for (int i = 0; i < n; ++i) {
skillToBit[skills[i]] = i;
}
// 每个人掌握技能的 bitmask 表示
vector<int> skillMasks(m, 0);
for (int i = 0; i < m; ++i) {
for (const string &skill: people[i]) {
if (skillToBit.count(skill)) {
skillMasks[i] |= (1 << skillToBit[skill]);
}
}
}
// dp[i][s] 表示从第 i 个人开始，当前技能状态为 s 时，最少需要多少人才能完成
vector<vector<int>> dp(m, vector<int>(1 << n, -1));
// 计算最小团队人数
int minTeamSize = dfs(skillMasks, m, n, 0, 0, dp);
// 回溯构造答案
vector<int> res;
for (int i = 0, s = 0; s != (1 << n) - 1 && i < m; ++i) {
// 如果 s 还没凑齐就已经来到最后一个人，说明加入这最后一个人 s 就能凑齐
// 如果跳过 i 号人后的值和当前值不同，说明选择了 i 号人
if (i == m - 1 || dp[i][s] != dp[i + 1][s]) {
res.push_back(i);
s |= skillMasks[i]; // 技能集合更新
}
}
return res;
}
// 记忆化搜索函数
// arr: 每个人掌握的技能状态，m: 总人数，n: 技能数
// i: 当前第几个人，s: 当前已覆盖技能状态
// 返回：从 i 开始覆盖所有技能至少需要多少人
int dfs(const vector<int> &arr, int m, int n, int i, int s, vector<vector<int>> &dp) {
// 所有技能已覆盖
if (s == (1 << n) - 1) return 0;
// 所有人都用完但技能还没覆盖，返回无效
if (i == m) return INT_MAX;
if (dp[i][s] != -1) return dp[i][s];
// 情况1：不选当前这个人
int option1 = dfs(arr, m, n, i + 1, s, dp);
// 情况2：选当前这个人
int option2 = INT_MAX;
int next = dfs(arr, m, n, i + 1, s | arr[i], dp);
if (next != INT_MAX) option2 = 1 + next;
// 取最小值并记忆化
dp[i][s] = min(option1, option2);
return dp[i][s];
}
};
T386911 最长上升子序列输出解
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
const int MAXN = 100001;
vector<int> nums(MAXN); // 输入数组
vector<int> dp(MAXN); // dp[i]：从 i 开始的最长递增子序列长度
vector<int> min_end(MAXN); // min_end[i]：长度为 i+1 的递增子序列结尾的最小值（从大到小）
vector<int> res(MAXN); // 最终答案序列
int n, k;
// min_end 逆序
// 二分查找：在 min_end[0..len-1] 中找 <= target 的最左位置
// 失败时返回 len
int bs(int len, int target) {
int l = 0, r = len - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (min_end[m] <= target) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
// 构建 dp 表，返回 LIS 的长度
int build_dp() {
int len = 0;
for (int i = n - 1; i >= 0; --i) {
int pos = bs(len, nums[i]);
if (pos == len) {
min_end[len++] = nums[i];
dp[i] = len;
} else {
min_end[pos] = nums[i];
dp[i] = pos + 1;
}
}
return len;
}
// 构建字典序最小的最长递增子序列
// 此处字典序不是常规意义上的字典序，是把每个整数当作一个“单独的字符”来看，而不是按整串组合来比谁字符串更小。
void lis() {
k = build_dp();
fill(res.begin(), res.begin() + k, INT_MAX);
for (int i = 0; i < n; ++i) {
if (dp[i] == k) {
// 如果当前位置能作为 LIS 的第一个元素，直接设置
res[0] = nums[i];
} else {
// 如果 nums[i] 能作为 res[k - dp[i]]，且比前一位大，则更新
if (res[k - dp[i] - 1] < nums[i])
res[k - dp[i]] = nums[i];
}
}
for (int i = 0; i < k; ++i)
cout << res[i] << (i == k - 1 ? '\n' : ' ');
}
int main() {
while (cin >> n) {
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
lis();
}
return 0;
}
P1759 通天之潜水
- 多维费用背包
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
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;
const int MAXN = 105;
const int MAXM = 205;
int a[MAXN], b[MAXN], c[MAXN];
int dp[MAXN][MAXM][MAXM]; // dp[i][j][k]: 前i个物品，在容量为j、阻力为k的限制下的最大收益
string path[MAXN][MAXM][MAXM]; // 对应的字典序最小的路径
int m, v, n; // 最大重量、最大阻力、物品数量
void build() {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= v; ++k) {
dp[i][j][k] = 0;
path[i][j][k] = "";
}
}
}
}
void compute() {
string p2;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= v; ++k) {
// 情况1：不选第i个工具
dp[i][j][k] = dp[i - 1][j][k];
path[i][j][k] = path[i - 1][j][k];
// 情况2：尝试选第i个工具（下标从1开始）
if (j >= a[i] && k >= b[i]) {
int preVal = dp[i - 1][j - a[i]][k - b[i]] + c[i];
string prePath = path[i - 1][j - a[i]][k - b[i]];
if (!prePath.empty()) {
p2 = prePath + " " + to_string(i);
} else {
p2 = to_string(i);
}
if (dp[i][j][k] < preVal) {
dp[i][j][k] = preVal;
path[i][j][k] = p2;
} else if (dp[i][j][k] == preVal) {
if (p2 < path[i][j][k]) {
path[i][j][k] = p2;
}
}
}
}
}
}
}
int main() {
while (cin >> m >> v >> n) {
build();
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
compute();
cout << dp[n][m][v] << "\n";
cout << path[n][m][v] << "\n";
}
return 0;
}
- 空间压缩
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
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 最大工具数量
const int MAXN = 101;
// 最大背包容量与最大阻力值
const int MAXM = 201;
int n, m, v; // n：工具数量，m：背包容量限制，v：阻力限制
vector<int> a(MAXN), b(MAXN), c(MAXN); // a[i]：第i个工具的重量，b[i]：阻力，c[i]：增加的停留时间
vector<vector<int>> dp(MAXM, vector<int>(MAXM)); // dp[j][k]：在容量j、阻力k下的最大停留时间
vector<vector<string>> path(MAXM, vector<string>(MAXM)); // path[j][k]：对应最大停留时间的工具选择路径（字典序最小）
// 初始化 dp 和 path 表
void build() {
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= v; ++j) {
dp[i][j] = 0;
path[i][j].clear();
}
}
}
// 多维费用背包主过程（空间压缩版本）
void compute() {
for (int i = 1; i <= n; ++i) {
// 逆序遍历，确保每个工具只被选择一次
for (int j = m; j >= a[i]; --j) {
for (int k = v; k >= b[i]; --k) {
string p2;
// 构造路径字符串
if (path[j - a[i]][k - b[i]].empty()) {
p2 = to_string(i);
} else {
p2 = path[j - a[i]][k - b[i]] + " " + to_string(i);
}
int newTime = dp[j - a[i]][k - b[i]] + c[i];
if (dp[j][k] < newTime) {
// 情况1：可以更新最大停留时间
dp[j][k] = newTime;
path[j][k] = p2;
} else if (dp[j][k] == newTime) {
// 情况2：停留时间相等，选择字典序更小的路径
if (path[j][k].empty() || p2 < path[j][k]) {
path[j][k] = p2;
}
}
}
}
}
}
int main() {
while (cin >> m >> v >> n) {
build();
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
compute();
cout << dp[m][v] << "\n";
cout << path[m][v] << "\n";
}
return 0;
}
本文由作者按照 CC BY 4.0 进行授权