你也许会好奇为什么没有 04.16 的训练记录，昨天农了一天 O(∩_∩)O。
Vacation
小明在接下来的 \(n\) 天，可以选择三种事件并获得 \(a_i / b_i / c_i\) 的快乐值，但是他不能连续两天及以上做同样的事。问最大的欢乐值是多少？
\(n \leq 10^5; a_i, b_i, c_i \leq 10^4\)。
换句话说就是每天做的事情都不一样。用 \(f_{i, j}\) 表示第 \(i\) 天做 \(j\) 事件所得到的最大快乐值，枚举今天和明天做的事件，即：
\[f_{i + 1, j} = \max\{ f_{i + 1, j}, f_{i, k} + \{a, b, c\}_k \}, j \ne k
\]
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<std::array<int, 3>> h(n);
for (int i = 0; i < n; i++) {
std::cin >> h[i][0] >> h[i][1] >> h[i][2];
}
std::vector<std::array<int, 3>> f(n + 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) if (j != k) {
f[i + 1][j] = std::max(f[i + 1][j], f[i][k] + h[i][k]);
}
}
}
std::cout << *std::max_element(f.back().begin(), f.back().end()) << '\n';
return 0;
}
Knapsack 1
01 背包。
\(n \leq 100, w \leq 10^5, v_i \leq 10^9\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, w;
std::cin >> n >> w;
std::vector<ll> f(w + 1);
for (int i = 0; i < n; i++) {
int wi, ci;
std::cin >> wi >> ci;
for (int j = w; j >= wi; j--) {
f[j] = std::max(f[j], f[j - wi] + ci);
}
}
std::cout << f.back() << '\n';
return 0;
}
Knapsack 2
01 背包。
\(n \leq 100, w \leq 10^9, v_i \leq 10^3\)。
考虑 \(f_{i, j}\) 为前 \(i\) 个物品，得到 \(j\) 价值的最小容量。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, w;
std::cin >> n >> w;
const int N = n * 1000;
std::vector<std::vector<int>> f(n + 1, std::vector<int>(N + 1, 0x3f3f3f3f));
f[0][0] = 0;
for (int i = 0; i < n; i++) {
int wi, vi;
std::cin >> wi >> vi;
for (int j = 0; j <= N; j++) {
f[i + 1][j] = std::min(f[i + 1][j], f[i][j]);
if (j + vi <= N) {
f[i + 1][j + vi] = std::min(f[i + 1][j + vi], f[i][j] + wi);
}
}
}
for (int i = N; ~i; i--) {
if (f[n][i] <= w) {
std::cout << i << '\n';
std::exit(0);
}
}
return 0;
}
LCS
求两字符串 \(s, t\) 的最长公共子序列。
Longest Path
Grid 1
Coins
Sushi
Stones
Deque
Candies
Slimes
同合并石子，区间 dp 模板题。满足四边形不等式。
展开代码
#include <bits/stdc++.h>
int read() {
int x = 0, f = 1, c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); x = x * 10 + c - '0', c = getchar());
return x * f;
}
const int N = 410;
using ll = long long;
const ll inf = 1E18;
int n, a[N], s[N][N];
ll f[N][N], sum[N];
#define w(i, j) sum[j] - sum[i - 1]
int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
s[i][i] = i;
}
for (int l = 2; l <= n; l++) {
for (int i = 1, j = l; j <= n; i++, j++) {
f[i][j] = inf;
for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) {
if (f[i][j] > f[i][k] + f[k + 1][j] + w(i, j)) {
f[i][j] = f[i][k] + f[k + 1][j] + w(i, j);
s[i][j] = k;
}
}
}
}
printf("%lld\n", f[1][n]);
return 0;
}