动态规划 · 学习笔记
前言
本人动态规划的能力实在是太菜啦！于是写学习笔记整理心得。会记录做题时的思路，但不会讲解。
本文的目的并不是为了让初学者入门/教授高深的优化技巧，也不是讲解具体的 dp 算法，而是想让像我一样的选手理解动态规划的思路，提升思维能力，拥有解出动态规划/想出作为暴力的朴素 dp 的能力。
可以说，这篇文章讲授的并非是 dp，而是借助 dp 这种具有思维含量的题型总结提炼思维的方法论，使我自己获得提升，也同时使阅读本文的其他人获得提升。
本文可能会更新，麻烦管理员重复审核。\
近期本文会开很多新坑，但是更新速度难以保证。
为了使语言更清晰，本文中的部分内容使用了 AI 整理表述，但内容为本人原创。
本文食用指南
本文中的二级标题是我对 dp 的认识和理解的总结，下面的三级标题是该类型的杂题选讲。
总起：动态规划 · 五要素
状态 · 边界条件（初始化/答案）· 状态转移方程 · 推导顺序
这所有的要素中，以状态的定义最为重要。
状态设计类
状态设计 · P3205 [HNOI2010] 合唱队
看到这题，首先想到爆搜。但是数据范围不允许。
是计数，并且已经知道爆搜，考虑用动态规划。
考虑线性 dp。发现只知道最后的队列，由此无法定义（基于插入顺序的）状态。
试图定义基于最终序列的状态。
可以定义形如 dp[i] 代表最终序列的前 i 个元素插入的方案数。但是插入可以从前后两个方向进行。这么做有问题。
那么就设法解决这个问题。可以发现用区间 dp 能够解决。定义 dp[i][j] 表示最终序列的
边界条件显然：dp[i][i] = 1, ans = dp[1][n]。推导顺序也显然：按照区间 dp 的板子来就行了。
考虑状态转移。从 dp[i + 1][j] 到 dp[i][j] 的转移是显然的：直接将方案数加起来再取模。
但是在什么时候才能实现这样的转移呢？
这样相当于将某个元素插入了队头，那么它就比前面的元素小。
哪个元素才是前面的元素呢？不知道。无法转移。
重设状态。发现每个元素刚刚插入时要么在队头要么在队尾。这启示我们设计与队头/队尾有关的状态。
设 dp[i][j].first 为最终序列的 dp[i][j].seocnd 是从队尾插入的方案数。
之前的问题就可以解决了：上一个元素要么从队头插入，要么从队尾插入，分别考虑一下就知道了。用代码片段表示：
//h[i] 表示最终队形中第 i 个元素的值
if (h[i] < h[i + 1]) {
dp[i][j].first += dp[i + 1][j].first;
dp[i][j].first %= mod;
}
if (h[i] < h[j]) {
dp[i][j].first += dp[i + 1][j].second;
dp[i][j].first %= mod;
}
if (h[j] > h[j - 1]) {
dp[i][j].second += dp[i][j - 1].second;
dp[i][j].second %= mod;
}
if (h[j] > h[i]) {
dp[i][j].second += dp[i][j - 1].first;
dp[i][j].second %= mod;
}边界条件？dp[i][i] = {1, 1}？
发现过不了样例 问题在于只有一个元素时方案数只有一种，从头插和从尾插都是一样的。
钦定一种不存在就对了。
完整代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 19650827;
int n;
array<int, 1005> h;
array<array<pair<int, int>, 1005>, 1005> dp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> h[i];
dp[i][i] = {1, 0};
}
for (int len = 2; len <= n; ++len) {
for (int i = 1, j = len; j <= n; ++i, ++j) {
if (h[i] < h[i + 1]) {
dp[i][j].first += dp[i + 1][j].first;
dp[i][j].first %= mod;
}
if (h[i] < h[j]) {
dp[i][j].first += dp[i + 1][j].second;
dp[i][j].first %= mod;
}
if (h[j] > h[j - 1]) {
dp[i][j].second += dp[i][j - 1].second;
dp[i][j].second %= mod;
}
if (h[j] > h[i]) {
dp[i][j].second += dp[i][j - 1].first;
dp[i][j].second %= mod;
}
}
}
cout << (dp[1][n].first + dp[1][n].second) % mod;
return 0;
}从状态设计角度对 dp 进行优化 · P2285 [HNOI2004] 打鼹鼠
首先，dp[t][i][j] 为在时刻 t 处在
先解决空间问题。
解决方法很简单：时间这一维对转移并没有太大意义。记录当前点答案被达成的最早时间。每次转移时看两点之间的距离是否小于等于答案最早达成的时间与当前时间之差。
这样做为什么是对的呢？
luogu_gza 提醒了我：有一个重要的性质是每个点作为终点所能达到的最优答案一定随着时间的推移而单调不降。这是下面证明的前提。
如果某个点能够到达现在这个点的最晚时间比那个点的现有答案达成的时间更早的话，之前的答案就一定更小。现在的点最多出现一只鼹鼠，答案最多比先前的答案大一，一定小于等于那个点的现有答案。所以这样转移不会影响答案。
再考虑时间。
感觉没有鼹鼠出现过的点有些无用？能不能从这个角度入手优化时间复杂度？
我们可以仅从有鼹鼠出现过的点转移。从没有出现过鼹鼠的点不会影响答案，因为它们的答案都是从某个出现过的点转移来的，后来又不会增加，所以仅从有鼹鼠出现过的点转移来就可以了。
于是成功达到
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct option {
int time, ans;
};
array<array<option, 1005>, 1005> dp;
struct mouse {
int x, y, t;
mouse(int x, int y, int t) : x(x), y(y), t(t) {}
};
vector<mouse> mice;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y, t;
cin >> t >> x >> y;
mice.emplace_back(x, y, t);
}
for (int i = 0; i < m; ++i) {
const int x = mice[i].x, y = mice[i].y, t = mice[i].t;
dp[x][y].time = t;
for (int j = 0; j < i; ++j) {
if (t - dp[mice[j].x][mice[j].y].time >= abs(mice[j].x - x) + abs(mice[j].y - y)) {
dp[x][y].ans = max(dp[x][y].ans, dp[mice[j].x][mice[j].y].ans);
}
}
dp[x][y].ans++;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
ans = max(ans, dp[i][j].ans);
}
}
cout << ans;
return 0;
}一道神秘的 dp · P2679 [NOIP2015 提高组] 子串
看到这道神秘的题，我一时间毫无思路。
处于某种神秘的考虑 这题在线性 dp 题单里 我决定考虑 dp。
事实上，就算不知道这题在 dp 题单里，我们也有充分的理由考虑 dp：本题是一个计数问题，有明显的阶段划分（当前选定的子串的数量、当前子串的长度、当前正在与 B 中的哪个字符匹配）。这些很容易让我们想到线性 dp，也启发了我们对状态的设计。
于是，综合以上要素，可以设 dp[i][j][k] 为当前已经选定 i - 1 个子串，正在选第 i 个子串，当前子串已经选定 j 个字符，当前正在与 B 中的第 k 个字符匹配的方案数。
但是这样做会遇到一个问题：如果要从子串数更少的状态转移信息，需要对多个状态的方案数求和，时间会爆，实现也非常复杂。
重设状态。考虑设 dp[i][j][k].first/second 是选定 i 个子串，当前字符是 A 中的第 j 个，与 B 中的第 k 个字符匹配并且当前字符在/不在被选择的字符中的方案数。
记得要滚动数组，不然空间会爆。
如果一直输出零，想想 dp 数组里是不是有些该更新的地方没有更新。
模数比较大，多个数加一块的情况可能要先转 long long 再取模，不然会爆 int。
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int n, m, k;
basic_string<char> a, b;
array<array<array<pair<int, int>, 205>, 2005>, 5> dp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
cin >> a >> b;
int sum = 0;
for (int i = 1; i <= n; ++i) {
if (a[i - 1] == b[0]) {
dp[1][i][1].first = 1;
}
dp[1][i][1].second = sum;
sum += (a[i - 1] == b[0] ? 1 : 0);
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= n; ++j) {
int l;
if (i != 1) {
l = 1;
} else {
l = 2;
}
for (; l <= m; ++l) {
if (a[j - 1] == b[l - 1]) {
int x = (i <= 2 ? dp[i & 1][j][l].first : 0);
dp[i & 1][j][l].first = ((long long)x + dp[i & 1][j - 1][l - 1].first + dp[(i - 1) & 1][j - 1][l - 1].second + dp[(i - 1) & 1][j - 1][l - 1].first) % mod;
}
int x = (i <= 2 ? dp[i & 1][j][l].second : 0);
dp[i & 1][j][l].second = ((long long)x + dp[i & 1][j - 1][l].first + dp[i & 1][j - 1][l].second) % mod;
}
}
}
cout << (dp[k & 1][n][m].first + dp[k & 1][n][m].second) % mod;
return 0;
}P1541 [NOIP2010 提高组] 乌龟棋
本题的暴力并不难想：设 dp[i][j][k][l][m] 为当前正处于第 i 格，四种类型的卡牌分别用了 j k l m 张时能达到的最高分数，然后就是显然的状态转移与边界条件。
但是这样做显然会同时超出时空限制。
发现并不需要第一维：当所用的卡牌给定后，处在的位置就是确定的了。
设 dp[i][j][k][l] 为四种类型的卡牌分别用了 i j k l 张时能达到的最高分数。
转移时枚举每一个可能出现的卡牌状态，从上一次用了这些牌中的某张卡牌的状态转移。
#include <bits/stdc++.h>
using namespace std;
int n, m;
array<int, 10> cnt;
array<int, 400> a;
array<array<array<array<int, 45>, 45>, 45>, 45> dp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
int tmp;
cin >> tmp;
cnt[tmp]++;
}
for (int i = 0; i <= cnt[1]; ++i) {
for (int j = 0; j <= cnt[2]; ++j) {
for (int k = 0; k <= cnt[3]; ++k) {
for (int l = 0; l <= cnt[4]; ++l) {
if (i > 0) {
dp[i][j][k][l] = max(dp[i - 1][j][k][l], dp[i][j][k][l]);
}
if (j > 0) {
dp[i][j][k][l] = max(dp[i][j - 1][k][l], dp[i][j][k][l]);
}
if (k > 0) {
dp[i][j][k][l] = max(dp[i][j][k - 1][l], dp[i][j][k][l]);
}
if (l > 0) {
dp[i][j][k][l] = max(dp[i][j][k][l - 1], dp[i][j][k][l]);
}
dp[i][j][k][l] += a[i + j * 2 + k * 3 + l * 4 + 1];
}
}
}
}
cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]];
return 0;
}初识期望 dp · P4316 绿豆蛙的归宿
首先，不要把有向图当无向图建可以想到沿拓扑序 dp。
设 dp[i] 代表在点 i 到达终点的路径长度期望。
边界条件：dp[n] = 0，答案即为 dp[1]。
由于状态设计，沿拓扑序逆推。
每个点的期望是它能到达的点的期望对于它的期望的贡献的总和。
而一个点对当前点的贡献等于它的期望加上到达它的边权除以当前点的出度。
#include <bits/stdc++.h>
using namespace std;
int n, m;
array<int, 100005> in_deg;
array<vector<pair<int, int>>, 100005> e;
array<double, 100005> dp;
vector<int> order;
void topo_sort() {
queue<int> q;
q.push(1);
while (!q.empty()) {
int qaq = q.front();
q.pop();
order.push_back(qaq);
for (auto [i, w] : e[qaq]) {
in_deg[i]--;
if (in_deg[i] == 0) {
q.push(i);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, w);
in_deg[v]++;
}
topo_sort();
reverse(order.begin(), order.end());
// for (auto i: order) {
// cout << i << " ";
// }
for (auto i : order) {
for (auto [j, w] : e[i]) {
dp[i] += ((w + dp[j]) / e[i].size());
}
}
cout << fixed << setprecision(2) << dp[1];
return 0;
}分组背包 · ABC383F
这道题首先想到 dp。
考虑记 dp[i][option] 为当前正在转移第 i 个物品，已经使用过的物品为 option 的最优答案。
这是个状压，复杂度是指数，肯定不行。
那么考虑记 dp[i][j].first/second 为当前考虑到第 i 个物品，用不超过 j 元钱，之前用过/没用过该颜色的物品？
显然是错的。因为两个物品的颜色不一样，没用过之前那种物品的颜色不代表没有用过当前物品的颜色。
再仔细想想？这个问题是个背包的变种，并且相同颜色的物品之间有某种关联……对了！是分组背包。
由于只有相同颜色的物品之间存在相互关联，考虑将它们分为一组。
对于每一组物品，可以选其中的一个，也可以不选或选很多个。这就对应了状态转移方程：
dp[i][j] = max({
dp[i][j],
dp[i - 1][j],
dp[i - 1][j - p] + u + k,
dp[i][j - p] + u
});需要注意几个细节：
- 对于一组内的某个物品，转移枚举花费的钱数时要倒序枚举，因为转移时会用到同一组内更前（花费钱数更少）的状态，如果正序枚举的话就可能将同一个物品用多次，会变成完全背包。
- 注意每个转移时要让总钱数消耗小于当前物品价值的状态继承上一个组的状态不能直接不管。
- 注意转移时不仅要与三种可能取 max，也要与自己取 max，否则会覆盖掉同组的之前的物品的转移，会变成每组只能取一个物品的背包。
- 不开 long long 见祖宗。
放一个由于离散化写的很丑的代码：
#include <bits/stdc++.h>
using namespace std;
long long n, x, k, tot;
array<vector<long long>, 505> p, u;
array<array<long long, 50005>, 505> dp;
struct product {
long long u, c, p;
product(long long p, long long u, long long c) : p(p), u(u), c(c) {}
};
vector<pair<product, long long>> a(1, {{0, 0, 0}, 0});
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> x >> k;
for (long long i = 0; i < n; ++i) {
long long p, u, c;
cin >> p >> u >> c;
a.push_back({{p, u, 0}, c});
}
sort(a.begin() + 1, a.end(), [](auto x, auto y) -> bool {
return x.second < y.second;
});
for (long long i = 1; i < a.size(); ++i) {
if (a[i].second > a[i - 1].second) {
a[i].first.c = a[i - 1].first.c + 1;
} else {
a[i].first.c = a[i - 1].first.c;
}
}
for (auto [tmp, y]: a) {
if (tmp.c > 0) {
p[tmp.c].push_back(tmp.p);
u[tmp.c].push_back(tmp.u);
}
}
tot = a.back().first.c;
for (long long i = 1; i <= tot; ++i) {
for (long long j = 0; j < p[i].size(); ++j) {
for (long long l = x; l >= p[i][j]; --l) {
dp[i][l] = max(
{dp[i][l], dp[i - 1][l], dp[i - 1][l - p[i][j]] + u[i][j] + k, dp[i][l - p[i][j]] + u[i][j]});
}
for (long long l = 0; l < p[i][j]; ++l) {
dp[i][l] = max(dp[i - 1][l], dp[i][l]);
}
}
}
cout << dp[tot][x];
return 0;
}简单 dp · Three Strings
这道题被放在一个 ad-hoc 题单里，所以我一开始想的是贪心。
但是这里的“不匹配数”没有像字典序那样方便贪心的性质。再看一眼，发现数据范围支持
设 dp[i][j] 为用 a 的前 i 个字符与 b 的前 j 个字符来构造 c 的前 i + j - 1 个字符产生的最小不匹配数。
边界条件是 i 或 j 等于 0 的情况。这些情况是显然的。
对于 i != 0 && j != 0 的情况，考虑从用 a 中字符与用 b 中字符的情况取最优解。
统计答案时，应对所有合法（即使用不超过 a.size() 个 a 中字符和 b.size() 个 b 中字符构造整个 c）的情况取最小。
#include <bits/stdc++.h>
using namespace std;
int t;
array<array<int, 1005>, 1005> dp;
basic_string<char> a, b, c;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
for (int _ = 0; _ < t; ++_) {
cin >> a >> b >> c;
dp[0][0] = 0;
for (int i = 1; i <= a.size(); ++i) {
dp[i][0] = dp[i - 1][0] + (a[i - 1] == c[i - 1] ? 0 : 1);
}
for (int i = 1; i <= b.size(); ++i) {
dp[0][i] = dp[0][i - 1] + (b[i - 1] == c[i - 1] ? 0 : 1);
}
for (int i = 1; i <= a.size(); ++i) {
for (int j = 1; j <= b.size(); ++j) {
dp[i][j] = min(dp[i - 1][j] + (a[i - 1] == c[i + j - 1] ? 0 : 1),
dp[i][j - 1] + (b[j - 1] == c[i + j - 1] ? 0 : 1));
}
}
int ans = 1e9;
for (int i = 0; i <= c.size(); ++i) {
const int x = c.size() - i, y = i;
if (x <= a.size() && y <= b.size()) {
ans = min(ans, dp[x][y]);
}
}
cout << ans << "\n";
for (int i = 0; i <= a.size(); ++i) {
for (int j = 0; j <= b.size(); ++j) {
dp[i][j] = -1;
}
}
}
return 0;
}灵感到了一眼秒 · 数据结构优化 dp 思维好题
朋友推荐的一道题。没有提交入口，只有题面，口胡专用。
题意
给定长度为 n 的序列 a 和常数 k。你需要将 a 划分为若干非空连续子段，并满足每一段内逆序对数不超过 k。对划分方案数计数，输出方案总数对一个模数取模的结果。
解析
神秘计数题，首先想到 dp。由于本题需要与具体的序列有关，可以猜想不是组合计数，且一般这种题都是组合计数或 dp，使用排除法想到 dp。
按照这种题的惯用套路，我们先考虑设状态 dp[i][j]，代表前 i 个元素共划分了 j 段的方案数。
我们需要做的决策是决定是否切出新的一段。具体的，就是对于每个元素决定是将它划进上一段（当前的最后一段）还是另开一个新段。
然而我们发现，如果我们将这个元素划入上一段，那么之后逆序对数量有可能超过 k，这个操作就是不合法的。而根据上面的状态设计，我们无法确定将当前元素划入上一段后逆序对数是否会超标。
于是考虑加入新的一维，即当前段的起点。设 dp[i][j][k] 为前 i 个元素划分为 j 段，最后一段的起点为 k 的方案总数。
然后，此时我们的决策就可以对应到转移方程：
（枚举 i）
（枚举 j、k）
dp[i][j][k] = dp[i - 1][j][k];
（枚举 k）
（当 k 到 i-1 这一段内的逆序对数不超标时）
dp[i][j][i] += dp[i - 1][j - 1][k];这样，我们就有了一个
然后，我们发现，j 这一维并没有什么用处，我们仅使用 i 和 k 就已经具备了转移的“封闭性”，也即是足以刻画状态的所有性质。
于是，
接下来，如果要更进一步，就需要充分地发挥我们的注意力。
有一个关键洞察：任意一个连续段，都有一个起点。也即是说，就算这个新段不是在当前点开的，也必然会在之前的某个点开出来。
有了这样的关键性质，再尽力发挥想象力，我们会发现：这个性质与我们的二维 dp 状态中的第二维是紧密相关的。因为这个性质是关于每一段的起点的，dp 状态的第二维也是关于每一段的起点的，与这个性质关联密切。
dp 的建模 · [NOIP2011 普及组] 表达式的值
乍眼一看，此题和 dp 似乎毫无关系，反而与表达式求值紧密相关。
对于这种表达式类的题，通用做法是建表达式树。
我们发现，如果建出表达式树，这就变成了一个树形 dp 好题。
对于任意运算符节点，以它们为根的子表达式树对应的子表达式取真/假的方案数可以由它们左右两边的子树的值求出。
即若该节点为 * 节点，它取真当且仅当两边都取真，其余情况都取假。根据乘法原理，它取真的情况就是两边取真的情况的数量的乘积。+ 节点是类似的。
对于数字节点，它们取真和取假的方案各有一种。
于是就做完了，记得取模。
但是我放这个题其实是为了宣扬我建表达式树的方法：先给每个运算符赋优先级，然后去除括号。对一个区间的表达式建树时，先找出优先级最低的节点作为根，然后对于根两边的表达式递归建树。
对于此题，由于 len 的范围最大是
写的相当屎的代码。如果想看更多的表达式求值石山，戳这里：神秘的前中后缀表达式互相转换/求值
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 10007;
int len;
array<int, 100005> order;
array<array<int, 20>, 100005> max_val;
basic_string<char> expression;
inline int query(int l, int r) {
int x = __lg(r - l + 1), mid = r - (1 << x) + 1;
if (order[max_val[l][x]] < order[max_val[mid][x]]) {
return max_val[l][x];
} else {
return max_val[mid][x];
}
}
struct node {
bool type;
int true_count, false_count;//the number of solutions what can make the expression is true or false
node *left, *right;
explicit node(char ch) {
if (ch == '*') {
type = true;
} else {
type = false;
}
left = right = nullptr;
true_count = false_count = 0;
}
} *rt;
void build(int l, int r, node *&p) {
int pos = query(l, r);
p = new node(expression[pos]);
if (pos > l) {
build(l, pos - 1, p->left);
}
if (pos < r) {
build(pos + 1, r, p->right);
}
}
void calc(node *p) {
int lv1, lv2, rv1, rv2;
if (p->left) {
calc(p->left);
lv1 = p->left->true_count;
lv2 = p->left->false_count;
} else {
lv1 = lv2 = 1;
}
if (p->right) {
calc(p->right);
rv1 = p->right->true_count;
rv2 = p->right->false_count;
} else {
rv1 = rv2 = 1;
}
if (p->type) {
p->true_count = lv1 * rv1;
p->false_count = lv1 * rv2 + rv1 * lv2 + lv2 * rv2;
} else {
p->true_count = lv1 * rv2 + rv1 * lv2 + lv1 * rv1;
p->false_count = lv2 * rv2;
}
p->true_count %= mod;
p->false_count %= mod;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> len >> expression;
for (int i = 0, v = 0; i < len; ++i) {
if (expression[i] == '(') {
v += 3;
} else if (expression[i] == ')') {
v -= 3;
}
order[i] = v;
if (expression[i] == '*') {
order[i] += 2;
} else if (expression[i] == '+') {
order[i]++;
}
}
vector<int> non_brackets;
basic_string<char> tmp;
for (int i = 0; i < len; ++i) {
if (expression[i] != '(' && expression[i] != ')') {
non_brackets.push_back(i);
tmp.push_back(expression[i]);
}
}
len = tmp.size();
expression = '\0' + tmp;
for (int &non_bracket: non_brackets) {
non_bracket = order[non_bracket];
}
for (int i = 1; i <= len; ++i) {
order[i] = non_brackets[i - 1];
}
/*cout << expression << "\n";
for (int i = 1; i <= len; ++i) {
cout << order[i] << " ";
}
cout << "\n";*/
for (int i = len; i > 0; --i) {
max_val[i][0] = i;
for (int j = 1; (1 << j) + i - 1 <= len; ++j) {
if (order[max_val[i + (1 << (j - 1))][j - 1]] < order[max_val[i][j - 1]]) {
max_val[i][j] = max_val[i + (1 << (j - 1))][j - 1];
} else {
max_val[i][j] = max_val[i][j - 1];
}
}
}
build(1, len, rt);
calc(rt);
cout << rt->false_count;
return 0;
}小细节/小技巧
容易忽略的细节 · P4342 [IOI1998] Polygon
太板了，一眼断环为链，区间 dp 板子。
但是注意一点：乘法有负负得正，所以可能两个负数乘起来是一个很大的正数。dp 时不能仅存储最大值，还要存储最小值以防止出现两个绝对值巨大的负数乘起来是答案的情况。
因为断环为链，数组记得开两倍。
#include <bits/stdc++.h>
using namespace std;
int n;
array<int, 105> a, op;
array<array<int, 105>, 105> dp, g;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
char ch;
cin >> ch;
if (ch == 't') {
op[i] = op[i + n] = 1;
} else {
op[i] = op[i + n] = 2;
}
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1; i < 2 * n; ++i) {
for (int j = i + 1; j < 2 * n; ++j) {
dp[i][j] = -1e9;
g[i][j] = 1e9;
}
}
for (int i = 1; i < 2 * n; ++i) {
g[i][i] = dp[i][i] = a[i];
}
for (int len = 2; len <= n; ++len) {
for (int i = 1, j = len; j < 2 * n; ++i, ++j) {
for (int k = i; k < j; ++k) {
if (op[k + 1] == 1) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);
} else {
dp[i][j] = max({dp[i][j], dp[i][k] * dp[k + 1][j], dp[i][k] * g[k + 1][j], g[i][k] * g[k + 1][j], g[i][k] * dp[k + 1][j]});
g[i][j] = min({g[i][j], dp[i][k] * dp[k + 1][j], dp[i][k] * g[k + 1][j], g[i][k] * g[k + 1][j], g[i][k] * dp[k + 1][j]});
}
}
}
}
int ans = 0;
vector<int> edges;
for (int i = 1, j = n; j < 2 * n; ++i, ++j) {
if (dp[i][j] > ans) {
ans = dp[i][j];
edges.clear();
edges.push_back(i);
} else if (ans == dp[i][j]) {
edges.push_back(i);
}
}
cout << ans << "\n";
for (auto i : edges) {
cout << i << " ";
}
return 0;
}方案的记录 · P1854 花店橱窗布置
本题很板，没什么好讲的。唯一有价值的是方案的记录。
我们平时写的 dp 都只能求出最大/小的答案而不能记录取到这个答案的方案。要记录方案很简单：对于每一个状态，记录它是从之前的那个状态转移来的就行了。最后从最优解向前遍历，把最优解的前驱状态依次输出就行了。
不过应管理员的要求，写一下思路：
假设我们已经考虑到要进行 dp，那么不难想到设 dp[i][j] 为前 i 朵花放置在前 j 个花瓶中的最大价值。
原因是这是一个类似最长公共子序列的“序列匹配”的问题。不过那道题两个字符间匹配产生的权值只有 1 或 0，而这题给定了花与花瓶匹配产生的权值。
至于为什么要用 dp，将在“dp 的本质 · 如何判定一个问题应该使用线性 dp”一节下重新讲解。
#include <bits/stdc++.h>
using namespace std;
int f, v;
array<array<int, 105>, 105> a, dp, pos;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> f >> v;
for (int i = 1; i <= f; ++i) {
for (int j = 1; j <= v; ++j) {
cin >> a[i][j];
dp[i][j] = -1e9;
}
}
for (int i = 1; i <= f; ++i) {
for (int j = i; j <= v; ++j) {
for (int k = i - 1; k < j; ++k) {
if (dp[i][j] < dp[i - 1][k] + a[i][j]) {
dp[i][j] = dp[i - 1][k] + a[i][j];
pos[i][j] = k;
}
}
}
}
int ans = -1e9, last = 0;
for (int i = f; i <= v; ++i) {
if (dp[f][i] > ans) {
ans = dp[f][i];
last = i;
}
}
cout << ans << "\n";
stack<int, vector<int>> s;
for (int i = f; i >= 1; --i) {
s.push(last);
last = pos[i][last];
}
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}后效性 · “封闭性”/信息完备性
我们经常听到的“无后效性”其实是说，一个 dp 状态推导完成之后，无论之后怎么决策，该状态本身的值是不会变的。
也就是说，dp 的状态间的依赖关系形成的图没有环。
比如最长上升子序列，假设以第 i 个元素结尾的最长上升子序列已经确定，无论之后选择哪些元素续上，以这个元素结尾的最长上升子序列的长度是不会改变的。
“封闭性”，或者说“重叠子问题”，是说一个 dp 状态的转移只与它记录的那些信息有关。
例如背包，确定当前还剩多少钱和还有哪些物品可供选择后，最优解就是确定的了，而与具体购买了哪些物品无关。之后从这个状态转移时也不需要考虑状态内部购买了哪些物品。
换而言之，dp 状态是“封闭的”，外界只能也只需要看到它所提供的几个标签（对于背包来说就是总共多少钱、可用哪些物品以及最优解（最大价值）的数值）。
为什么说这和“重叠子问题”相同呢？
对于搜索而言，每个状态有很多其他的信息需要考虑。dp 的一个状态可能被视为很多不同但对于问题求解本质相同的子问题。也就是“重叠子问题”。
dp 相当于将这些子问题抽象成了同一个 dp 状态。
封闭性也可称之为信息完备性。即一个状态中的信息可以刻画它的全部性质，同一个状态对应的子问题应该具备完全相同的性质。这样就避免了贪心中常常遇到的一步最优，后续反而引入新的限制导致后续不优。
封闭性的概念在状压 dp 中会经常应用。
从封闭性的角度重看状压 dp 经典题 · 最短哈密顿路径
问题描述： 给定一个 n 个点的带权图，求一条从点 0 出发，经过每个顶点恰好一次，最终回到点 0 的路径，使得路径上的边权之和最小（即最短哈密顿路径）。
如果使用暴力搜索，我们需要枚举所有可能的路径，时间复杂度是阶乘级别的。
但是，我们观察到，如果已经确定了走过的点的集合，就可以推算出到达这个集合的最短路径长度。
例如，假设我们已经走过了点集 {1, 2, 3}，并且知道到达这个点集的所有路径中，最短路径长度为 10。那么无论我们当前在哪一个点（1，2 或 3），后续的决策都只需要基于这个最短路径进行扩展即可。
因为其他更长的路径到达 {1, 2, 3} 之后，最终得到的总路径长度一定不会更优。 这暗示我们可以利用动态规划来避免重复计算。
然而，直接使用“已走过的点的集合”作为状态是不够的。问题在于：这个状态的封闭性不完全。即使走过了相同的点集，例如 {1, 2, 3}，我们接下来走向其他点时的边的长度会受到当前所在点的影响。
假设当前在点 3，要走到点 4，那么边长就是 edge(3, 4)；如果当前在点 2，要走到点 4，那么边长就是 edge(2, 4)。
即使点集相同，到达点 4 的代价也可能不同。这意味着仅记录点集无法唯一确定后续的转移代价，状态不封闭。
为了解决这个问题，我们需要扩展状态的定义。我们不仅记录走过的点的集合，还需要记录当前所在的点。
这样，状态 dp[S][i] 就表示经过点集 S 且当前在点 i 的最短路径长度。这个状态是完全封闭的，因为给定 S 和 i，后续的转移代价就唯一确定了。
状态转移方程可以简述为：dp[S][i] = min{dp[S - {i}][j] + edge(j, i)}，其中 j 属于 S - {i}。这告诉我们要到达状态 dp[S][i]，我们可以枚举上一个点 j，从状态 dp[S - {i}][j] 转移过来，并加上边 (j, i) 的权重。
通过这种状态设计，我们成功地将问题转化为了一个具有封闭性的动态规划问题，从而可以高效地求解最短哈密顿路径。
间奏 · 如何判定一个问题必须使用区间 dp
如何判断一个问题是否必须使用区间 dp 而不能使用线性 dp 呢？这些问题有一个非常典型的特征。
那就是：在转移前面的状态时 需要后面的信息。线性 dp 做这类问题时会产生后效性。
这样讲太抽象不好理解，让我们举几个例子。
-
合并石子\ 本题就具备这个典型的特征：规划前若干个石子合并的最优解时需要考虑到前面石子和后面石子合并的可能性，所以只知道前若干个石子的最优解无法向后面转移。
-
括号序列类问题\ 括号是一前一后的，单单找前括号并不能有效的转移。
-
之前讲的 P3025\ 这道题也是同时在当前队列的一前一后插入。
dp 的本质 · 如何判定一个问题应该使用线性 dp
对于 dp 的题，一个难点就是看出它应该使用 dp。对于树形/状压/dag 等类型的 dp，特征较为明显，较容易辨认。但对于线性和区间 dp，要认出它们就较为困难了。
我们在各种地方应该都听过 dp 的本名：多阶段决策最优化/计数问题的递推解法。这个名称蕴含着 dp 的本质，也指引着我们发现如何判断一个问题要用 dp 的方法。
稍微具体的，我们在初学 dp 时可能会听说 dp 具有明显的决策阶段性。
可以拆分为多个不同的决策，且这些决策关系很复杂，难以像贪心那样简单地找出最优解正是 dp 的重要特征。
更进一步的，贪心的核心条件是在当前阶段即可判定哪中决策一定更优，而 dp 则不具备此种条件。因为不能确定哪种决策更优，于是 dp 将所有的决策路径都以状态的形式保留下来，并留待以后考虑。
保留所有状态，与搜索的“遍历所有状态”有类似性，这也是可以从搜索出发考虑 dp 的原因。
从 dp 的决策本质重看封闭性与后效性，就会发现封闭性本质上是：对于若干种决策路径，只要能够判定哪种更优，就立刻合并它们，保留最优路径继续进行下面的递推，将其他的不优路径都舍弃。无后效性则是为了保证总可以判定这些路径哪个更优并合并它们。
CF2025D Attribute Checks
我对此题的题解
题目的具体解法在上方的题解中。我们仅讨论如何看出这是线性 dp 的题目。
可以发现，这是一个多阶段决策的最优化问题，决策的阶段是当前处理的记录的索引（下标），我们要做出的决策是在获得一个点数时决定将其分配到智力或体力上，并且最大化通过的检测次数。
我们注意到，我们不能在处理到一个获得点数的操作时立刻确定将该点数分配到哪个属性上面更优。
这是上述的典型 dp 特征。另外，由于阶段（正在处理的操作的下标）之间的递推关系是线性的，并且我们是按照阶段以线性的方式递推处理的，所以这是一个线性 dp 问题。
然后，考虑设置状态。由于无法立刻确定哪种决策路径更优，我们将它们全部保留。但是这样就变成了搜索。
从封闭性的角度考虑。我们发现，无论之前分配点数的过程是怎样的，只要智力和力量两种属性都分别相同，那么之后的检测通过状况就一定是相同的。
于是就只需要保留智力和力量（以及下标）在状态中了。
并且智力和力量的和一定等于当前获得的总点数，而我们的转移一定是从上一个阶段出发的，所需要考虑的所有状态一定都是同一“时间”（阶段）的，也就可以省去智力和力量中的一维。
如何想到要用 DP · 重讲 P1854 花店橱窗布置
面对 P1854 花店橱窗布置 这道题，我们的目标是 “取得最佳的美学效果”，也即在保持花束顺序的前提下，使花的摆放取得最大的美学值。 这明确地告诉我们，这是一个 最优化问题，我们需要找到一种摆放方案，使得总的美学值最大。
初步分析： 决策和阶段性
仔细阅读题面，我们可以发现，我们需要做的核心决策是： 为每一束花选择一个合适的花瓶。并且，这些决策是 有顺序的，我们可以 按照花束的编号顺序 依次决定每束花放在哪个花瓶里。
这就是问题的 阶段性： 决策可以按花束的顺序划分阶段，当前阶段的决策 (为当前花束选择花瓶) 会影响后续阶段的决策 (为后续花束选择花瓶)。
需要注意的是，我们并没有被要求按照编号顺序做决策。只是因为编号靠前的花的决策会影响后面的决策，我们处于状态转移的方便才制造了一种顺序。
在 dp 中，很多转移顺序并不是题目的强制要求，而是我们出于解题方便的需要，根据题目中各决策之间的依赖、影响关系，结合题目特点人为制造的。
贪心策略的尝试与分析
我们可能会首先考虑使用 贪心策略。
例如，对于每一束花，都选择能产生最大美学值的花瓶来放置。
然而，贪心策略在这种情况下很可能失效。 因为题目的约束条件 (花束顺序和花瓶顺序) 使得 局部最优选择并不一定能保证全局最优。
为什么贪心失效？ 决策的复杂性
贪心失效的根本原因在于，在每个阶段 (为当前花束选择花瓶) 做决策时，我们 无法简单地判断哪种选择在全局上更优。 因为把当前花束放在一个美学值很高的花瓶里，可能会导致后续的花束没有足够的花瓶可选，或者只能选择美学值很低的花瓶。 当前的选择会限制未来的可能性，影响全局的总美学值。 这种 决策之间的复杂关联，使得贪心策略难以奏效。
转向动态规划： 多阶段决策的最优化问题
由于贪心策略无法保证全局最优，并且问题具有 明显的阶段性 (按花束顺序决策) 和 最优化目标 (最大化美学值)， 这就引导我们考虑使用 动态规划 (DP) 来解决。 DP 正是擅长解决多阶段决策最优化问题，它通过 保留所有可能的决策路径，并在后续阶段进行 选择和优化，来找到全局最优解。
DP 的核心思想： 保留所有可能，递推求解最优
DP 的核心思想是 避免重复计算，利用子问题的最优解来构建原问题的最优解。 为了应用 DP，我们需要：
- 定义合适的状态： 状态需要能够描述问题的 “进展情况” 和 “决策结果”，即满足 无后效性 和 最优子结构（封闭性）。
- 推导状态转移方程： 状态转移方程描述了如何从已知的子问题的解，递推计算当前问题的解。
- 确定边界条件和推导顺序： 确定 DP 的初始状态和计算顺序，最终得到问题的答案。
具体的，就是我们之前讲解这道题时的分析。这里不再重复。
DP的再思考：最优子结构、贪心与状态合并
在学习DP的过程中，我们总会听到“最优子结构”这个词。教科书上对它的定义往往是“一个问题的最优解包含其子问题的最优解”，这句话听起来正确但又非常抽象，让人不知道它究竟有什么用。
后来我发现，这个性质至关重要，它其实是动态规划，乃至很多优化算法能够成立的 “贪心许可证”。
最优子结构：贪心的许可证
“最优子结构”更直白的解释是：如果状态A比状态B更优，那么从状态A出发能达到的最优未来状态，都将比从状态B出发能达到的任意未来状态更优。（或至少不劣），也就是，A 演化出的未来必定包含一个最优解。
这个性质给了我们一个极其强大的能力：状态合并。当我们有多种方式可以达到同一个“中间状态”时，我们完全可以贪心地只保留那个最优的方式，而把其他所有较差的方式全部丢弃。因为“许可证”向我们保证，这些被丢弃的路径，未来也绝无翻盘的可能。
这个过程，本质上就是在执行一次贪心。DP之所以强大，就在于它精妙地运用了这种贪心。
从最短路看“分类贪心”
为了理解这一点，我们来看两个我们很熟悉的最短路算法：SPFA和Dijkstra。
-
SPFA/Bellman-Ford：动态规划的体现 SPFA的本质是一个动态规划。它的状态
dist[u]代表“从起点s到顶点u的当前已知最短路”。它的状态转移方程就是松弛操作：dist[v] = min(dist[v], dist[u] + weight(u, v))。 SPFA的过程，就是不断用已知状态去更新其他状态，直到无法再更新为止。它允许一个点的dist值被多次更新，这和我们做背包DP时，dp[j]的值被不同物品更新是类似的。它很“稳健”，因为它没有做太强的假设，只是在不断地、系统地进行状态合并（松弛操作就是一种状态合并）。 -
Dijkstra：带限制的贪心 Dijkstra算法则是一个纯粹的贪心算法。它在每一步都做出一个不可撤销的贪心决策：从所有“未确定最短路”的顶点中，选择一个
dist值最小的顶点u，并宣布dist[u]就是最终的最短路。 为什么Dijkstra可以这么贪心？它的“许可证”是什么？是 “所有边权非负” 这个更强的限制。 正是因为边权非负，Dijkstra才能保证：一旦u是当前dist最小的未确定点，那么任何其他路径都不可能再通过一个未确定点绕回来，从而得到一条到u的更短路径了。这个限制让它的贪心选择变得 绝对安全。
DP 与贪心的光谱：分类的智慧
现在，我们可以揭示DP与贪心的真正关系了。
DP能够进行状态合并的本质是，它将状态“分类”。对于同一类状态，它们中在答案属性上更优的，不会因为引入了额外的限制而使得未来扩展出的新状态（比该类中其他状态扩展出的）不优。而贪心没有进行这个分类。它假设，对于任意两个状态，更优的一定产生的新状态也一定更优。
更具体的：
-
动态规划 = 分类后的贪心 DP的智慧在于，它承认世界是复杂的，未来的可能性有很多。所以它把所有可能的中间局面划分成不同的等价类（Equivalence Classes），也就是我们定义的状态。 例如，在背包问题中，
dp[i][w]就是一个等价类，它代表“考虑完前i个物品，当前背包重量恰好为w”的所有方案。在这个类内部，我们根据“最优子结构”这张许可证，贪心地只保留价值最大的那个方案。 DP并没有像纯贪心那样，在dp[i][w]和dp[i][w+1]之间也进行贪心比较。它把这些不同类别的最优代表都保留了下来，因为它知道“重量为w”和“重量为w+1”是两种不同的未来，都需要被考虑。 -
贪心算法 = 不分类的绝对贪心 纯贪心算法则认为，在任何时刻，都只有一个最优的“等价类”，那就是“当前看起来最好的选择”。它在所有可能的下一步中，直接选出那个局部最优解，然后义无反顾地走下去，抛弃了所有其他的可能性。 当问题的性质（如Dijkstra的非负边权，或活动选择的结束时间排序）能保证这种“绝对贪心”的正确性时，它就非常高效。但当这种保证不存在时，它就会因为“一叶障目”而错失全局最优解。
总结来说，DP是一种更审慎、更聪明的贪心。它通过“状态”这个工具对问题进行分类，在每个分类内部大胆贪心，在分类之间则小心翼翼地保留各种可能性。理解了这一点，我们就能更深刻地把握何时该用DP，何时可以简化为贪心，以及如何设计出那个能够支撑我们进行“分类贪心”的完美状态。