动态规划中根据数据量猜解法
根据数据规模选择动态规划方法，数据大用优化状态压缩，小数据用朴素枚举，平衡时间与空间复杂度。
动态规划中根据数据量猜解法
动态规划中根据数据量猜解法
打怪兽
- a[i] 范围大，b[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
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
// 方法1：a[i] 范围大，b[i] 范围小的适用版本
// 时间复杂度：O(n * 所有怪兽的钱数累加和)
int fc(int n, const vector<int> &a, const vector<int> &b) {
int m = 0;
for (int i = 1; i <= n; i++) m += b[i];
// dp[i][j] : 花的钱不能超过j，通过前i个怪兽，最大能力是多少
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MIN));
dp[0][0] = 0; // 初始能力为0，花费为0
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 如果上一个状态在 j 金钱下的能力 >= 当前怪兽所需能力，可以直接通过
if (dp[i - 1][j] >= a[i])
dp[i][j] = dp[i - 1][j];
// 如果选择贿赂怪兽
if (j >= b[i] && dp[i - 1][j - b[i]] != INT_MIN)
dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + a[i]);
}
}
for (int j = 0; j <= m; j++)
if (dp[n][j] != INT_MIN)
return j;
return -1;
}
int main() {
int n;
while (cin >> n) {
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
cout << fc(n, a, b) << '\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
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
// 方法2：方法1的空间优化版本
int fc(int n, const vector<int> &a, const vector<int> &b) {
int m = 0;
for (int i = 1; i <= n; i++) m += b[i];
vector<int> dp(m + 1, INT_MIN);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
int cur = INT_MIN;
if (dp[j] >= a[i])
cur = dp[j];
if (j >= b[i] && dp[j - b[i]] != INT_MIN)
cur = max(cur, dp[j - b[i]] + a[i]);
dp[j] = cur;
}
}
for (int j = 0; j <= m; j++)
if (dp[j] != INT_MIN)
return j;
return -1;
}
int main() {
int n;
while (cin >> n) {
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
cout << fc(n, a, b) << '\n';
}
return 0;
}
- a[i] 范围小，b[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
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
// 方法3：a[i] 范围小，b[i] 范围大的适用版本
// 时间复杂度：O(n * 所有怪兽能力累加和)
int fc(int n, const vector<int> &a, const vector<int> &b) {
int m = 0;
for (int i = 1; i <= n; i++) m += a[i];
// dp[i][j] : 能力正好是j，并且确保能通过前i个怪兽，需要至少花多少钱
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 如果当前能力 j >= 当前怪兽要求，能力不变，不花钱
if (j >= a[i] && dp[i - 1][j] != INT_MAX)
dp[i][j] = dp[i - 1][j];
// 贿赂怪兽，能力提升 a[i]，代价加 b[i]
if (j >= a[i] && dp[i - 1][j - a[i]] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[i - 1][j - a[i]] + b[i]);
}
}
int res = INT_MAX;
for (int j = 0; j <= m; j++)
res = min(res, dp[n][j]);
return (res == INT_MAX ? -1 : res);
}
int main() {
int n;
while (cin >> n) {
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
cout << fc(n, a, b) << '\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
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
// 方法4：方法3的空间优化版本
int fc(int n, const vector<int> &a, const vector<int> &b) {
int m = 0;
for (int i = 1; i <= n; i++) m += a[i];
vector<int> dp(m + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
int cur = INT_MAX;
if (j >= a[i] && dp[j] != INT_MAX)
cur = dp[j];
if (j >= a[i] && dp[j - a[i]] != INT_MAX)
cur = min(cur, dp[j - a[i]] + b[i]);
dp[j] = cur;
}
}
int res = *min_element(dp.begin(), dp.end());
return (res == INT_MAX ? -1 : res);
}
int main() {
int n;
while (cin >> n) {
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
cout << fc(n, a, b) << '\n';
}
return 0;
}
选择k个数字使得两集合累加和相差不超过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
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <numeric>
using namespace std;
// 选择k个数字使得两集合累加和相差不超过1
// 给定一个正数n，表示1~n这些数字都可以选择
// 给定一个正数k，表示要从1~n中选择k个数字组成集合A，剩下数字组成集合B
// 希望做到集合A和集合B的累加和相差不超过1
// 如果能做到，返回集合A选择了哪些数字，任何一种方案都可以
// 如果不能做到，返回长度为0的数组
// 2 <= n <= 10^6
// 1 <= k <= n
// 根据总和和k值生成一个可行的方案（返回选择了哪些数）
// sum：期望子集A的累加和
// n：范围是1~n
// k：A集合要挑选k个数字
vector<int> generate(long long sum, int n, int k) {
long long minKSum = (long long) (k + 1) * k / 2; // 最小选择前k个数的和
int range = n - k; // 剩余数字的可操作范围
// 如果目标sum太小或太大，无法达到
if (sum < minKSum || sum > minKSum + (long long) range * k) return {};
// 需要在最小基础上增加的值
long long need = sum - minKSum;
int rightSize = need / range; // 选择几个最大的数放到集合中
int midIndex = (k - rightSize) + (need % range); // 中间的那个调整值
int leftSize = k - rightSize - (need % range == 0 ? 0 : 1); // 前缀部分
vector<int> res(k);
for (int i = 0; i < leftSize; i++)
res[i] = i + 1;
if (need % range != 0)
res[leftSize] = midIndex;
for (int i = k - 1, j = 0; j < rightSize; i--, j++)
res[i] = n - j;
return res;
}
// 主方法
vector<int> pick(int n, int k) {
long long sum = (long long) (n + 1) * n / 2;
// 先尝试总和的一半
vector<int> res = generate(sum / 2, n, k);
// 再尝试 +1（奇数情况下）
if (res.empty() && (sum & 1))
res = generate(sum / 2 + 1, n, k);
return res;
}
// 记忆化搜索判断是否能划分（验证用）
bool fc(int n, int i, int k, int s, vector<vector<vector<int>>> &dp) {
if (k < 0 || s < 0) return false;
if (i == n + 1) return k == 0 && s == 0;
if (dp[i][k][s] != 0) return dp[i][k][s] == 1;
bool res = fc(n, i + 1, k, s, dp) || fc(n, i + 1, k - 1, s - i, dp);
dp[i][k][s] = res ? 1 : -1;
return res;
}
bool canSplit(int n, int k) {
int sum = (n + 1) * n / 2;
int wantSum = sum / 2 + (sum % 2);
vector<vector<vector<int>>> dp(n + 2, vector<vector<int>>(k + 1, vector<int>(wantSum + 1)));
return fc(n, 1, k, wantSum, dp);
}
// 判断一个方案是否正确（对数器验证）
bool pass(int n, int k, const vector<int> &res) {
if (res.empty()) {
return !canSplit(n, k);
} else {
if ((int) res.size() != k) return false;
int sum = (n + 1) * n / 2;
int pickSum = accumulate(res.begin(), res.end(), 0);
return abs(pickSum - (sum - pickSum)) <= 1;
}
}
// 对数器：随机生成数据验证
int main() {
srand(time(0));
int N = 60;
int testTime = 5000;
cout << "测试开始" << endl;
for (int i = 0; i < testTime; ++i) {
int n = rand() % N + 2;
int k = rand() % n + 1;
vector<int> res = pick(n, k);
if (!pass(n, k, res))
cout << "出错了！n = " << n << ", k = " << k << endl;
}
cout << "测试结束" << endl;
return 0;
}
P1439 【模板】最长公共子序列
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
#include <iostream>
#include <vector>
using namespace std;
// ends 逆序
// 二分查找，在 ends[0...len) 中找第一个 >= target 的位置
// 失败时返回 len
int binarySearch(const vector<int> &ends, int len, int target) {
int l = 0, r = len - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] >= target) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
// 计算最长公共子序列长度
int fc(int n, const vector<int> &a, vector<int> &b) {
vector<int> where(n + 1); // where[x] = x 在 a 中的位置
for (int i = 0; i < n; i++)
where[a[i]] = i;
// 将 b 映射为 a 中的索引序列，问题转为 LIS
for (int i = 0; i < n; i++)
b[i] = where[b[i]];
// LIS 求解
vector<int> ends(n); // ends[i] 代表长度为 i+1 的最小结尾值
int len = 0;
for (int i = 0; i < n; i++) {
int pos = binarySearch(ends, len, b[i]);
if (pos == len) {
ends[len++] = b[i]; // 增加新的子序列长度
} else {
ends[pos] = b[i]; // 替换已有的最小结尾值
}
}
return len;
}
int main() {
int n;
while (cin >> n) {
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
cout << fc(n, a, b) << '\n';
}
return 0;
}
1187. 使数组严格递增
- 记忆化搜索
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
// 记忆化搜索解法
int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
// 排序并去重
sort(arr2.begin(), arr2.end());
int m = 1;
for (int i = 1; i < arr2.size(); i++)
if (arr2[i] != arr2[m - 1])
arr2[m++] = arr2[i];
int n = arr1.size();
vector<int> dp(n, -1); // 记忆化数组，初始化为 -1
int res = dfs(arr1, arr2, n, m, 0, dp);
return res == INT_MAX ? -1 : res;
}
// arr1 长度为 n，arr2 有效部分长度为 m
// arr2 有效部分可以替换 arr1 中的数字
// arr1[0..i-1] 已经严格递增且 arr1[i-1] 一定没有替换
// 返回让 arr1 整体都严格递增，arr1[i...] 范围上还需要几次替换
// 如果做不到，返回无穷大
int dfs(vector<int> &arr1, vector<int> &arr2, int n, int m, int i, vector<int> &dp) {
if (i == n) return 0;
if (dp[i] != -1) return dp[i];
int res = INT_MAX; // 遍历所有的分支，所得到的最少的操作次数
int pre = i == 0 ? INT_MIN : arr1[i - 1]; // 前一位的数字
int find = binarySearch(arr2, m, pre); // arr2 有效长度 m 的范围上，找到刚比 pre 大的位置
// 枚举arr1[i...] 范围上，第一个不需要替换的位置 j
for (int j = i, k = 0, next; j <= n; j++, k++) {
if (j == n) {
res = min(res, k); // 全部换完了
} else {
if (pre < arr1[j]) { // 可以不换
next = dfs(arr1, arr2, n, m, j + 1, dp);
if (next != INT_MAX) res = min(res, k + next);
}
if (find < m) {
pre = arr2[find++]; // 尝试替换
} else {
break; // 替换失败，退出循环
}
}
}
dp[i] = res;
return res;
}
// 在 arr2[0..len-1] 中找第一个大于 target 的位置
// 失败时返回 len
int binarySearch(vector<int> &arr2, int len, int target) {
int l = 0, r = len - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (arr2[m] > target) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
};
- 严格位置依赖
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int binarySearch(vector<int> &arr2, int len, int target) {
int l = 0, r = len - 1, m;
while (l <= r) {
m = (l + r) / 2;
if (arr2[m] > target) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
// 动态规划解法
int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
int m = arr2.size();
int n = arr1.size();
// dp[i]：从第 i 位开始需要的最少替换次数
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int res = INT_MAX;
int pre = i == 0 ? INT_MIN : arr1[i - 1];
int find = binarySearch(arr2, m, pre);
for (int j = i, k = 0, next; j <= n; j++, k++) {
if (j == n) {
res = min(res, k);
} else {
if (pre < arr1[j]) {
next = dp[j + 1];
if (next != INT_MAX) {
res = min(res, k + next);
}
}
if (find < m) {
pre = arr2[find++];
} else {
break;
}
}
}
dp[i] = res;
}
return dp[0] == INT_MAX ? -1 : dp[0];
}
};
本文由作者按照 CC BY 4.0 进行授权