OI笔记 | 线性 DP 专题
最长公共子序列
给定一个长度为 $n$ 的序列 $A$ 和 一个长度为 $m$ 的序列 $B$（$n, m \le 5000$），求出一个最长的序列，使得该序列既是 $A$ 的子序列，也是 $B$ 的子序列。
题解
用 $dp_{i,j}$ 表示只考虑 $A$ 的前 $i$ 个元素， $B$ 的前 $j$ 个元素时最长公共子序列的长度，则答案为 $dp_{n,m}$。
对于 $dp_{i,j}$，如果 $A_i = B_j$，则把它接到 $dp_{i-1,j-1}$ 代表的公共子序列的末尾。否则，我们跳过 $A_i$ 或者跳过 $B_j$。于是得到状态转移方程：
\[dp_{i,j}=\begin{cases}dp_{i-1,j-1}+1&A_i=B_j\\\max(dp_{i-1,j},dp_{i,j-1})&A_i\ne B_j\end{cases}\]逆推回去，即可输出一个具体的最长子序列。这部分可以看动画演示(sourceforge)。
参考代码：
string a, b;
int dp[MAX_N][MAX_N];
int LCS_length() {
int n = a.length(), m = b.length();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
void LCS_print(int i, int j) {
if(i == 0 || j == 0) return;
if(a[i - 1] == b[j - 1]) LCS_print(i - 1, j - 1), putchar(a[i - 1]);
else if(dp[i - 1][j] >= dp[i][j - 1]) LCS_print(i - 1, j);
else LCS_print(i, j - 1);
}
[例题1] 编辑距离
设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
$A, B$ 均只包含小写字母。
题解
我们用 $dp_{i,j}$ 表示考虑 $A$ 的前 $i$ 位， $B$ 的前 $j$ 位的编辑距离。那么对于我们当前考虑的一对 $(i, j)$，假设在它之前的全部已经计算过答案，于是它可能由以下几种情况转移过来：
-
若 $A_i=B_j$，可以无需操作：$dp_{i,j} = dp_{i-1,j-1}$。
-
若 $A_i\neq B_j$，可以用一次操作将 $A_i$ 替换成 $B_j$： $dp_{i,j} = dp_{i-1,j-1}+1$。
-
考虑 $dp_{i-1,j}$ 已经能使 $A$ 的前 $i - 1$ 位与 $B$ 的前 $j$ 位对齐。所以可以用一次操作把 $A_i$ 删掉：$dp_{i,j} = dp_{i-1,j}+1$。
-
考虑 $dp_{i,j-1}$ 已经能使 $A$ 的前 $i$ 位与 $B$ 的前 $j-1$ 位对齐。所以可以用一次操作添加一个 $B_j$：$dp_{i,j} = dp_{i,j-1}+1$。
我们在这四种情况里取最小的即可。
注意初始化：显然 $dp_{i,0} = i$， $dp_{0,j}=j$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2005;
int dp[MAX_N][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
string a, b;
cin >> a >> b;
int n = a.length(), m = b.length();
for(int i = 1; i < max(n, m) + 1; i++) dp[0][i] = dp[i][0] = i;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j - 1] + !(a[i - 1] == b[j - 1]);
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
}
}
write(dp[n][m]);
return 0;
}
[例题2] 嗲串
如果一个字符串的长度为偶数且前一半和后一半完全一样，那么这个串被称为嗲串。现在给你一个字符串 $S$ ，请你回答：最少需要删掉几个字符，使得剩下的字符串是一个嗲串。
数据范围：$1\le \lvert S\rvert \le50$
题解
把字符串以 $k$ 为分界线分为两半($1 \le k < \lvert S\rvert$)。 对于每一个 $k$，跑一遍 LCS 即可。
int solve() {
int ans = s.length(), len = s.length();
for(int k = 1; k < len; k++) {
string a = s.substr(0, k);
string b = s.substr(k);
ans = min(ans, len - LCS_length(a, b) * 2);
}
return ans;
}
最长上升子序列
给定一个长度为 $n$ 的序列 $A$（$n\le 5000$），求出一个最长的 $A$ 的子序列，满足该子序列的后一个元素大于前一个元素。
动态规划
考虑用 $dp_i$ 表示必须以 $a_i$ 为结尾的上升子序列的最大长度。于是有状态转移方程： $dp_i = \max_{1\le j<i, a_j<a_i}(dp_j+1)$。
答案即为 $\max_{1\le i\le n}dp_i$。时间复杂度：$O(n^2)$。
参考代码：
int n, a[MAX_N], dp[MAX_N];
int LIS() {
int ans = 1;
for(int i = 1; i <= n; i++) {
a[i] = read();
dp[i] = 1;
for(int j = 1; j < i; j++) if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
return ans;
}
贪心+二分
时间复杂度： $O(n\log n)$。
我们维护一个最优子序列 $dp$。对于一个元素 $a_i$：
-
如果它比 $dp$ 的最后一个元素大，直接插入到 $dp$ 的末尾。
-
否则，插入到 $dp$ 中第一个大于等于它的位置。
这么做的正确性容易证明。
参考代码：
int n, a[MAX_N], dp[MAX_N];
int LIS() {
int ans = 0;
memset(dp, 0x1f, sizeof(dp));
int mx = dp[0];
for(int i = 1; i <= n; i++) *lower_bound(dp + 1, dp + n + 1, a[i]) = a[i];
while(dp[ans + 1] != mx) ans++;
return ans;
}
[例题] 导弹拦截
给定序列 $A$，问 $A$ 的 最长单调不升子序列的长度 和 把 $A$ 分割成若干单调不升子序列的最小个数。
题解
第一问很简单，经典 LIS 模型，写个二分即可。
第二问考虑使用 Dilworth 定理：将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的长度。于是再写一遍 LIS 即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5+7;
int a[MAX_N], dp[MAX_N];
inline void write(ll x) {...}
int main() {
int x, k = 1, ans = 1;
while(cin >> x) a[k++] = x;
memset(dp, -1, sizeof(dp));
for(int i = 1; i < k; i++) {
int l = 0, r = k;
while(l < r - 1) {
int mid = (l + r) >> 1;
if(dp[mid] >= a[i]) l = mid;
else r = mid;
}
dp[r] = a[i];
}
while(dp[ans] != -1) ans++;
write(ans - 1); putchar('\n');
ans = 1;
memset(dp, 0x1f, sizeof(dp));
for(int i = 1; i < k; i++) {
int l = 0, r = k;
while(l < r - 1) {
int mid = (l + r) >> 1;
if(dp[mid] >= a[i]) r = mid;
else l = mid;
}
dp[r] = a[i];
}
while(dp[ans] != dp[0]) ans++;
write(ans - 1); putchar('\n');
return 0;
}
01背包
有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
题解
考虑用 $dp_j$ 表示容量为 $j$ 的背包能装的最大价值。依次枚举每一个物品，于是它可以从两个状态转移过来：
-
不选第 $i$ 个物品， $dp_j$ 不变。
-
选第 $i$ 个物品， $dp_j = dp_{j-w_i} + v_i$。
我们只需要取两种情况中较大的一种。注意，对于每一件物品，要从 $W$ 枚举到 $w_i$，这样 $dp_j$ 总是在 $dp_{j-w_i}$ 前被更新，不会导致同一件物品多次放入背包的错误。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 105, MAX_V = 1005;
int w[MAX_N], v[MAX_N], dp[MAX_V];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int W = read(), n = read();
for(int i = 1; i <= n; i++) w[i] = read(), v[i] = read();
for(int i = 1; i <= n; i++) for(int j = W; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
write(dp[W]);
return 0;
}
如果要统计方案数，可以把 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); 改为 dp[j] += dp[j - w[i]];。
01背包输出方案
你能负载 $M$ 的重量与 $V$ 的阻力。每个物品有它的重量 $a_i$、阻力 $v_i$、价值$w_i$。对于每个物品，你可以选也可以不选。求你能获得的最大价值，以及你选择的物品。
题解
求最大价值这个 subtask 没什么好说的。
考虑输出方案，我们在做 01背包 的时候，记录下对于第 $i$ 件物品，有 $j$ 的负重和 $k$ 的最大阻力的状态 $(i,j,k)$ 有没有被选择。之后可以使用递归来输出方案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 205;
int M, V, n, a[MAX_N], b[MAX_N], v[MAX_N], dp[MAX_N][MAX_N];
bool f[MAX_N][MAX_N][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void print(int i, int j, int k) {
if(f[i][j][k]) {
if(i != 1) print(i - 1, j - a[i], k - b[i]);
write(i);
putchar(' ');
}
else if(i != 1) print(i - 1, j, k);
}
int main() {
M = read(), V = read(), n = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
b[i] = read();
v[i] = read();
}
for(int i = 1; i <= n; i++) {
for(int j = M; j >= a[i]; j--) {
for(int k = V; k >= b[i]; k--) {
if(dp[j - a[i]][k - b[i]] + v[i] > dp[j][k]) {
dp[j][k] = dp[j - a[i]][k - b[i]] + v[i];
f[i][j][k] = 1;
}
}
}
}
write(dp[M][V]); putchar('\n');
print(n, M, V);
return 0;
}
多重背包转化为01背包
多重背包如果把每件物品拆分，就变成01背包了。
当然最好是不要直接拆成单独的，可以用二进制优化，例如 $x = 12 = 1 + 2 + 4 + 5$，就把 $x$ 拆成 $1,2,4,5$ 四组捆绑的物品。
砝码称重
设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚（其总重$ \le 1000$），可以表示成多少种重量？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int w[] = {0, 1, 2, 3, 5, 10, 20};
vector<int> a;
int f[1005];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int V = 0, ans = 0;
for(int i = 1; i <= 6; i++) {
int x = read();
for(int j = 1; j <= x; j++) a.push_back(w[i]), V += w[i];
}
f[0] = 1;
for(int i = 0; i < a.size(); i++) {
for(int j = V; j >= a[i]; j--) {
f[j] += f[j - a[i]];
}
}
for(int i = 1; i <= V; i++) if(f[i]) ans++;
printf("Total=%d", ans);
return 0;
}
摆花
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e6 + 7, MAX_N = 105;
int dp[MAX_N], a[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
dp[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
for(int k = 1; k <= min(a[i], j); k++)
(dp[j] += dp[j - k]) %= MOD;
write(dp[m]);
return 0;
}
宝物筛选
二进制拆分的多重背包模板。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 105, MAX_W = 4e4 + 10;
int v[MAX_N], w[MAX_N], m[MAX_N], dp[MAX_W];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), W = read();
for(int i = 1; i <= n; i++) {
v[i] = read();
w[i] = read();
m[i] = read();
}
for(int i = 1; i <= n; i++) {
for(int k = 1; k <= m[i]; m[i] -= k, k *= 2) {
for(int j = W; j >= k * w[i]; j--) {
dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
}
}
if(m[i]) {
for(int j = W; j >= m[i] * w[i]; j--) {
dp[j] = max(dp[j], dp[j - m[i] * w[i]] + m[i] * v[i]);
}
}
}
write(dp[W]);
return 0;
}
完全背包
有 $n$ 种物品和一个容量为 $W$ 的背包，每种物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干个物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
题解
只需要把01背包的枚举顺序改为从 $w_i$ 到 $W$ 即可。这样相当于可以重复地选择。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 10005;
const int MAX_W = 1e7+3;
int w[MAX_N], v[MAX_N];
ll dp[MAX_W];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int W = read(), m = read();
for(int i = 1; i <= m; i++) w[i] = read(), v[i] = read();
for(int i = 1; i <= m; i++)
for(int j = w[i]; j <= W; j++)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
write(dp[W]);
return 0;
}
分组背包
有 $n$ 件物品和一个大小为 $W$ 的背包，第 $i$ 个物品的价值为 $w_i$，体积为 $v_i$。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。
题解
相当于我们对每一个组内部做一遍01背包，再对所有组做一个01背包。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1005;
int w[MAX_N][MAX_N], v[MAX_N][MAX_N];
ll dp[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int W = read(), m = read(), cnt = 0;
for(int i = 1; i <= m; i++) {
int t_w = read();
int t_v = read();
int k = read();
w[k][++w[k][0]] = t_w;
v[k][++v[k][0]] = t_v;
cnt = max(cnt, k);
}
for(int i = 1; i <= cnt; i++)
for(int j = W; j >= 0; j--)
for(int k = 1; k <= w[i][0]; k++)
if(j - w[i][k] >= 0)
dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);
write(dp[W]);
return 0;
}
以上几种背包的混合练习： 洛谷 P1833
其他题目
城市里的间谍(A Spy in the Metro)
某城市地铁是线性的，有 $n$（$2\leq n\leq 50$）个车站，从左到右编号 $1\ldots n$。有 $M_1$ 辆列车从第 $1$ 站开始往右开，还有 $M_2$ 辆列车从第 $n$ 站开始往左开。列车在相邻站台间所需的运行时间是固定的，因为所有列车的运行速度是相同的。在时刻 $0$，Mario 从第 $1$ 站出发，目的是在时刻 $T$（$0\leq T\leq 200$）会见车站 $n$ 的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的时间尽量短。列车靠站停车时间忽略不计，且 Mario 身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario 也能完成换乘。
题解
从紫书上学会了这道题的解法。首先我们预处理出来数组 $f$ 来查询某一时刻某一车站是否有车经过。例如 $f_{i,j,0}=1$ 表示在 $i$ 时刻， $j$ 车站有向右开的火车。
然后考虑 $dp$ 的设计。 我们用 $dp_{i, j}$ 表示当前位于 $i$ 时刻， $j$ 车站的情况下与间谍汇合需要的最少时间，则答案为 $dp_{0,1}$。显然应该初始化 $dp_{T, n}=0$，其他数为正无穷。
于是对于每对 $(i, j)$，都有 $3$ 种不同的决策：
-
原地等 $1$ 分钟： $dp_{i,j}=dp_{i+1,j}$。
-
若有向右开的火车，搭乘它： $dp_{i,j}=dp_{i+t_i, j+1}$。
-
若有向左开的火车，搭乘它： $dp_{i,j}=dp_{i+t_{i-1}, j-1}$。
每次取其中最小的那个，按时间逆序遍历，转移出结果即可。
注意有多组数据，记得清空数组。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_T = 205, MAX_N = 55;
ll t[MAX_T], dp[MAX_T][MAX_N];
bool f[MAX_T][MAX_N][2];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int ks = 1, n, T;
while((n = read()) != 0) {
memset(f, 0, sizeof(f));
T = read();
for(int i = 1; i <= n - 1; i++) t[i] = read();
int m1 = read();
for(int i = 1; i <= m1; i++) {
int x = read();
for(int k = 1; k <= n && x <= T; k++) f[x][k][0] |= 1, x += t[k];
}
int m2 = read();
for(int i = 1; i <= m2; i++) {
int x = read();
for(int k = n; k >= 1 && x <= T; k--) f[x][k][1] |= 1, x += t[k - 1];
}
memset(dp[T], 0x7f, sizeof(dp[T]));
dp[T][n] = 0; int INF = dp[T][0];
for(int i = T - 1; i >= 0; i--) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i + 1][j] + 1;
if(f[i][j][0] && j < n && i + t[j] <= T) dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]);
if(f[i][j][1] && j > 1 && i + t[j - 1] <= T) dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]);
}
}
printf("Case Number %d: ", ks++);
if(dp[0][1] < INF) write(dp[0][1]), putchar('\n');
else printf("impossible\n");
}
return 0;
}
小b和环
小b有一个长度为n的环，每个点上有个数字。（ $0\le $ 每个点上的数字 $\le 10000$ ）
现在请你选出一些点，满足选出的任意两个点在环上不相邻，且选出的点的数字之和最大，你只需输出这个最大值。
题解
动态规划。首先考虑链上的情况，用 $dp_{i,0}$ 表示不选 $i$ 上的数的最大值， $dp_{i,1}$ 表示选上 $i$ 上的数的最大值。则转移方程如下：
$dp_{i, 0} = \max(dp_{i-1,0}, dp_{i-1,1})$
$dp_{i, 1} = dp_{i-1, 0} + a_i$
再考虑环上的情况，这相比于链只多了一个限制，即不能同时选 $i$ 和 $n$。我们只需要分两类：选 $i$ 不选 $n$ ，选 $n$ 不选 $i$。做两遍 $dp$，比较这两种哪个更大即可。注意到两个都不选是更不优的方案，无需考虑。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int a[MAX_N], dp1[MAX_N][2], dp2[MAX_N][2];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++) {
dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][1]);
dp1[i][1] = dp1[i - 1][0] + a[i];
}
for(int i = 2; i <= n; i++) {
dp2[i][0] = max(dp2[i - 1][0], dp2[i - 1][1]);
dp2[i][1] = dp2[i - 1][0] + a[i];
}
write(max(dp1[n][0], dp2[n][1]));
return 0;
}
数组的最大代价
数组 $B$ 包含 $N$ 个元素 $B_1,B_2\dots B_N$。你来挑选一些数，生成一个数组 $A$。要求：
数组 $A$ 包含 $N$ 个元素 $A_1,A_2\dots A_N$。并且数组 $A$ 中的每一个元素 $A_i$，都满足 $1\le A_i \le B_i$。数组 $A$ 的代价定义如下：
$S=\sum\limits_{i = 2}^N\lvert A_i−A_{i−1}\rvert $
给出数组 $B$，计算数组 $A$ 可能的最大代价 $S$。
题解
考虑对于每一个 $A_i$，最优解的情况下它要么取下界 $1$，要么取上界 $B_i$。
我们用 $dp_{i,0}$ 表示位置 $i$ 取 $1$ 的最大代价，$dp_{i,1}$ 表示位置 $i$ 取 $B_i$ 的最大代价，于是有状态转移方程如下：
$dp_{i, 0} = \max{dp_{i-1, 0}+(1-1), dp_{i-1,1}+(B_{i-1}-1)}$
$dp_{i, 1} = \max{dp_{i-1,0}+(B_{i}-1), dp_{i-1, 1}+\lvert B_i-B_{i-1} \rvert}$
写成代码即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int a[MAX_N], dp[MAX_N][2];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 2; i <= n; i++) {
dp[i][0] = max(dp[i - 1][1] + a[i - 1] - 1, dp[i - 1][0]);
dp[i][1] = max(dp[i - 1][0] + a[i] - 1, dp[i - 1][1] + abs(a[i] - a[i - 1]));
}
write(max(dp[n][0], dp[n][1]));
return 0;
}
小明与回转寿司
小明正在日料店品尝回转寿司。料理师傅共准备做 $m$ 盘寿司，从第 $0$ 时刻起，每隔一段时间他就会完成一盘寿司放到传送带上。其中第 $i$ 盘寿司会在 $t_i$ 时刻来到小明面前，小明需要 $s_i$ 时间吃完并获得 $p_i$ 的饱腹值。
由于另有安排，小明必须在 $x$ 时刻停止食用。请你帮小明规划取哪些寿司，以获得最大的饱腹值。（$1\le m\le 100000$， $1\le t_i,s_i\le 10^9$，$1\le x\le 10^9$，$1\le p_i\le 10^9$）
注：日料店规定顾客必须吃完自己拿的每一盘寿司，并且吃完一盘才能拿下一盘。
题解
我们考虑对时刻做$dp$，用 $dp_t$ 表示到第 $t$ 时刻所能获得的最大价值，则答案为 $dp_x$。然而如果按照题目给的 $t$ 的范围，这样做是不切实际的。所以我们可以对时刻进行离散化，只存下对我们有用的时间点。离散化要用 $O(m\log m)$ 实现，离散化后的 $dp$ 是 $O(m)$ 的，所以总的时间复杂度为 $O(m\log m)$。状态转移方程如下：
-
一般情况下，有 $dp_t = \max(dp_t, dp_{t-1})$；
-
如果在 $t$ 时刻可以吃某个寿司 $i$，则可以转移到时刻 $t+s_i$，所以有 $dp_{t+s_i}=\max(dp_{t+s_i},dp_t+w_i)$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5+10;
struct task {
int l, r, w;
} tasks[MAX_N]; // 存储每一个寿司的起始点、终点和价值
set<int> T; // 用于保存每一个有效时间点，并且有序化
map<int, int> mp; // 用于将 T 里保存的时间点映射到可以接受的范围内
vector<int> time_task[MAX_N]; // time_task[t] 存储以 t 时刻为起始点的所有寿司的编号
ll dp[MAX_N]; // dp[t] 为到 t 时刻可以获得的最大价值
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int m = read(), x = read();
for(int i = 1; i <= m; i++) {
tasks[i].l = read();
tasks[i].r = read() + tasks[i].l;
tasks[i].w = read();
T.insert(tasks[i].l);
T.insert(tasks[i].r);
}
T.insert(x);
int rank = 1;
for(set<int> ::iterator it = T.begin(); it != T.end(); it++)
mp[*it] = rank++; // 离散化的实现
x = mp[x];
for(int i = 1; i <= m; i++) {
// 将 task 里存的时刻改为离散化后的时刻
tasks[i].l = mp[tasks[i].l];
tasks[i].r = mp[tasks[i].r];
// 将任务存到起始时刻上
time_task[tasks[i].l].push_back(i);
}
// 状态转移方程的实现
for(int i = 1; i <= x; i++) {
dp[i] = max(dp[i], dp[i - 1]);
for(int j = 0; j < time_task[i].size(); j++) {
task tmp = tasks[time_task[i][j]];
dp[tmp.r] = max(dp[tmp.r], dp[i] + tmp.w);
}
}
write(dp[x]);
return 0;
}
小b和排序
小 b 有两个长度都为 $n$ 的序列 $A$, $B$。
现在她需要选择一些 $i$，然后交换 $A_i$ 和 $B_i$，使得 $A$ 和 $B$ 都变成严格递增的序列。
你能帮小 b 求出最少交换次数吗？
其中 $1\le n\le 1000$，$0\le A_i,B_i\le 2000$，输入保证有解。
题解
正式开始学动态规划的第一题。
考虑用 $dp_{i, 0}$ 表示不交换第 $i$ 位的最少交换次数， $dp_{i, 1}$ 表示交换第 $i$ 位的最少交换次数。
则容易得出：
$dp_{i,0} = \min(dp_{i-1, 0}, dp_{i-1,1})$，
$dp_{i,1} = \min(dp_{i-1, 0}, dp_{i-1,1})+1$。
然而这些转移有条件。
当且仅当 $a_i > a_{i-1} $ 且 $b_i> b_{i-1}$ 时，我们可以同时交换 $i-1$ 与 $i$ 两个位置；也可以都不交换。
当且仅当 $a_i > b_{i-1} $ 且 $b_i> a_{i-1}$ 时，我们可以交换 $i-1$ 而不交换 $i$；也可以交换 $i$ 而不交换 $i-1$。
其他情况下的交换是非法的。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 10003;
int dp[MAX_N][2], a[MAX_N], b[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++) b[i] = read();
dp[0][0] = 0;
dp[0][1] = 1;
for(int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = 1e9;
if(a[i - 1] < a[i] && b[i - 1] < b[i]) {
dp[i][0] = min(dp[i][0], dp[i - 1][0]);
dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);
}
if(a[i - 1] < b[i] && b[i - 1] < a[i]) {
dp[i][0] = min(dp[i][0], dp[i - 1][1]);
dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
}
}
write(min(dp[n][0], dp[n][1]));
return 0;
}
小明爱爬山
小明非常喜欢爬山，但是小明爬上有一个癖好，就是只往高处走，就是说他下一步位置的海拔要比当前位置要高，现在小明拿到一个地图，地图上标明了每个地方的海拔，现在小明想要知道他在随意选择起点的情况下最多可以走几步？
(小明只可以向上下左右四个方向行走，且只能走比当前位置海拔高的位置)
题解
考虑每一个位置作为终点时，到达它最多可以走多少步。由于它只能从四个方向上比自己低的位置转移过来，可以采用记忆化搜索。
时间复杂度 $O(mn)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1005;
int dp[MAX_N][MAX_N], a[MAX_N][MAX_N], f[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, ans;
inline ll read() {...}
inline void write(ll x) {...}
int dfs(int x, int y) {
if(dp[x][y]) return dp[x][y];
int ret = 0;
for(int i = 0; i <= 3; i++) {
int tx = x + f[i][0];
int ty = y + f[i][1];
if(tx < 1 || ty < 1 || tx > n || ty > m) continue;
// 如果 (tx, ty) 是 (x, y)合法的前驱，它对应的最大步数可以参与比较
if(a[tx][ty] < a[x][y]) ret = max(ret, dfs(tx, ty));
}
return dp[x][y] = ret + 1;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = read();
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) ans = max(ans, dfs(i, j));
write(ans);
return 0;
}♥