线性 DP-最长上升子序列
最长上升子序列
1、最长上升子序列(easy)：给定一个长度为 $n$ 的数组 $a$ ($n \leq 1000$)，求其最长上升子序列(非降)的长度。注意：子序列不一定是连续的
2、对于线性 DP，通常用 $dp[i]$ 表示以 $i$ 结尾或到 $i$ 为止，如果有对应的代价，通常用 $dp[i][j]$ 表示到 $i$ 为止花费 $j$ 的代价的价值最值(见背包问题)
3、确定状态：令 $dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度
4、确定转移：对于输入的每一个 $a[i]$ ，可知都有两种情况：一种是它作为最长上升子序列的起点，另一种是它接续在其他上升子序列之后。对于 $a[i]$ 作为起点，$dp[i] = 1$ ；对于 $a[i]$ 作为接续，应向左搜寻一个 $j \lt i$，$dp[i] = max(dp[i], dp[j] + 1)$ ，遍历取最大值。总结状态转移方程为：
$$ \left\{ \begin{array}{l} dp[i] = 1 &作为起点 \\\\ dp[i] = max(dp[i], dp[j] + 1) &作为接续 \\\end{array} \right. $$
5、易知，该算法复杂度为 $O(n^2)$，只能处理小规模数据，仍需优化代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N], dp[N]; // 以 i 为终点的最长上升子序列长度 void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { dp[i] = 1; // 对于每个点，都可以先作为起点 // 找左侧比当前点小的点，状态转移 for (int j = 1; j < i; j++) if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1); } // 找最长的上升子序列 int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dp[i]); cout << ans; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }单调栈二分优化
1、最长上升子序列(hard)：在上题基础上，数组长度 $n$ 改为 $n \leq 2 \times 10^5$
2、在遍历求 $dp[i]$ 的过程中，可知：对于点 $i$ 在接续时，其左侧点 $j$ ，如果 $dp[j]$ 最长且 $a[j]$ 最小，那么点 $i$ 接续到点 $j$ 后一定为最优，因此需要维护一个单调栈(单调不减的单调栈，维护栈顶为 $dp[j]$ 最长且 $a[j]$ 最小的点的位置)
3、这个单调栈在维护时需要一些特殊操作，所以需要在原模型上改良一下：当准备入栈的元素 $i$ 的 $a[i]$ 比栈顶元素单调不减时，将 $i$ 入栈，$dp[i] = dp[top] + 1$ (从栈顶元素转移)；当准备入栈的元素 $i$ 的 $a[i]$ 比栈内某些元素小时，并不是从栈顶向下依次出栈再取代(因为并不满足 $dp[i]$ 最长的条件)，而是找到栈内第一个 $k \gt a[i]$ ，将其取代，$dp[i] = dp[k]$ (从元素 $k$ 转移，且长度与其相同)
4、例如 $\{2, 5, 3, 4, 7, 3\}$：当第一个 $3$ 需要入栈时($i = 2$)，单调栈内元素为 $\{2, 5\}$，应找到第一个大于 $3$ 的元素——$5$，将其替换，此时 $dp[i] = dp[1] = 2$ ($1$ 为元素 $5$ 的位置)，栈内变为 $\{2, 3\}$ (显然子序列 $\{2, 3\}$ 比 $\{2, 5\}$ 更优秀)；当第二个 $3$ 需要入栈时($i = 5$)，单调栈内元素为 $\{2, 3, 4, 7\}$，应找到第一个大于 $3$ 的元素——$4$，将其替换，此时 $dp[i] = dp[3] = 3$ ($3$ 为元素 $4$ 的位置)，栈内变为 $\{2, 3, 3, 7\}$ (其实际子序列为 $\{2, 3, 3\}$，长度为 $3$)
5、对于查找的操作，可以使用二分查找，但因为其需要操作下标，所以单调栈的实现应该使用数组实现，不能使用STL的stack。此外，由于只需要最长上升子序列的长度，所以单调栈的长度就是最长上升子序列的长度，不再需要 $dp[]$ 数组，栈内也不需要维护点的位置，而是可以直接维护 $a[i]$#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N], stk[N], top = 0; // 用数组实现单调栈 void solve() { int n, ans = 0; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { // pos 即 a[i] 在单调栈中的位置 // 找单调栈中第一个 > a[i] 的下标 = 最后一个 <= a[i] 的下标 + 1 int pos = (upper_bound(stk + 1, stk + 1 + top, a[i]) - stk - 1) + 1; // 如果 pos 超出了 top 栈顶的位置，说明 a[i] 比栈顶单调不减 if (pos == top + 1) ++top; // 拓展单调栈长度，相当于拓展最长子序列长度 stk[pos] = a[i]; // 入栈 或 取代位置 // top，单调栈的长度，就是目前最长上升子序列的长度 ans = max(ans, top); } cout << ans; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
线性 DP-导弹拦截
导弹拦截
1、导弹拦截：有导弹拦截系统，对于每个系统，其首发可以拦截任意高度的导弹，之后发射的每一发都不能高于前一发的高度。输入来袭的导弹高度(导弹数不超过 $1000$，高度不超过 $30000$)，询问如果只有一套系统时最多能拦截多少发，以及需要多少套系统才能全部拦截，依次输出
2、第一问询问的是最长下降子序列(非升)的长度，类似于最长上升子序列，使用单调栈实现。显然，当准备入栈的元素 $i$ 的 $a[i]$ 比栈内某些元素大时，查找栈内第一个 $k \lt a[i]$，将其替换。其余细节与先前相似
3、第二问询问最少需要多少套系统。需要根据狄尔沃斯定理：如果要使用最少个数的非升子序列覆盖一整个数组，其所需序列数量等同于最长的相反规则子序列的长度，此处即最长上升子序列的长度。因此需要求最长上升子序列的长度，即为答案
4、对于最长上升子序列，应维护一个严格单调递增栈。当准备入栈的元素 $i$ 的 $a[i]$ 大于栈顶元素时，才可以入栈；当准备入栈的元素 $i$ 的 $a[i]$ 小于等于栈内某些元素时；查找栈内第一个 $k \geq a[i]$ ，将其替换。其余细节与先前相似代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N]; int stk[N], top = 0; void solve() { // 输入数据 int n = 0; while (cin >> a[++n]) ; --n; // 求最长非升子序列长度 int ans = 0; for (int i = 1; i <= n; i++) { // upper_bound 原先用于查找第一个 > a[i] 的元素的位置 // 查找第一个 < a[i] 的元素的位置，由于 stk 是降序，所以使用 lambda 更改 upper_bound 的比较规则 int pos = (upper_bound(stk + 1, stk + 1 + top, a[i], [](const int &u, const int &v) { return u > v; }) - stk - 1) + 1; // pos 指向栈顶之上的位置，入栈，top++ if (pos == top + 1) top++; // 替换 pos 位置的元素，更新 ans stk[pos] = a[i]; ans = max(ans, top); } cout << ans << '\n'; // 初始化 top = 0, ans = 0; // 求最长上升子序列长度 for (int i = 1; i <= n; i++) { // lower_bound 用于查找第一个 >= a[i] 的元素的位置 // 查找第一个 >= a[i] 的元素的位置 int pos = (lower_bound(stk + 1, stk + 1 + top, a[i]) - stk - 1) + 1; // pos 指向栈顶之上的位置，入栈，top++ if (pos == top + 1) top++; // 替换 pos 位置的元素，更新 ans stk[pos] = a[i]; ans = max(ans, top); } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
线性 DP-摆花
摆花
1、摆花：一共有 $n$ 种花，按 $1 \to n$ 标号，$m$ 个盆，进行摆花，其中对于每种花不得超过 $a_i$ 盆($n, m, a_i \leq 100$)。摆花时，同种花放在一起，不同种类花按照标号从小到大排列。输出共有多少种方案，结果对 $10^6 + 7$ 取模
2、对于条件中的 $a_i$ 可解读为第 $i$ 种花只有 $a_i$ 盆，由数据量较小可以推断大致允许 $O(n*m*a_i)$ 的复杂度，此外不同种类花应由题意按标号从小到大选择
3、确定状态：令 $dp[i][j]$ 表示到第 $i$ 种花为止，一共放了 $j$ 盆花的总方案数
4、确定转移：假设当前有 $2$ 种花，$4$ 个盆，$a[1] = 3, a[2] = 2$，为方便理解可手算可能性共 $2$ 种，即 $\{1,1,2,2\}, \{1,1,1,2\}$ 。当 $i=2, j=4$ 时，思考 $dp[2][4]$ 的转移(到第 $2$ 种花为止一共放了 $4$ 盆)，有多种情况：令 $k$ 表示当前需要讨论的第 $i$ 种花放了 $k$ 盆(此例当前即第 $2$ 种花放了 $k$ 盆)；当 $k=0$ 时，$dp[2][4] += dp[1][4]$ (要使第 $2$ 种花放 $0$ 盆，其需要到第 $1$ 种花已经摆了 $4$ 盆)；当 $k=1$ 时，$dp[2][4] += dp[1][3]$ (要使第 $2$ 种花放 $1$ 盆，其需要到第 $1$ 种花已经摆了 $3$ 盆)；当 $k=2$ 时，$dp[2][4] += dp[1][2]$；因为 $a[2] = 2$ 只有 2 盆，所以上述为全部的可能。综上，可以总结：$dp[i][j] += dp[i-1][j-k]$，其中$k <= min(a[i], j)$
5、初始化：$dp[1][j] = 1$，其中$j \leq a[i]$，到第 $1$ 种花摆任意多盆都只有 $1$ 种摆法，从 $i=2$ 开始转移；也可以直接令 $dp[0][0] = 1$ 从 $i=1$ 开始转移，也能转移出 $dp[1][j] = 1$代码实现
#include <bits/stdc++.h> using namespace std; const int N = 110; const int P = 1e6 + 7; int a[N], dp[N][N]; // 到第 i 种花一共摆了 j 盆的总方案数 void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; // 初始化(也可以直接写 dp[0][0] = 1) for (int j = 0; j <= a[1]; j++) dp[1][j] = 1; // 到第 i 种花(如果初始化 dp[0][0] = 1 则应从 i=1 开始转移) for (int i = 2; i <= n; i++) // 一共摆了 j 盆 for (int j = 0; j <= m; j++) // 其中第 i 种花摆了 k 盆 for (int k = 0; k <= a[i] && k <= j; k++) // 状态转移，取模 dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % P; cout << dp[n][m]; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
区间 DP-石子合并
石子合并
1、石子合并：有 $n$ 个石子排成一列($n \leq 300$)，给出每个石子的质量 $m_i$。每次可以合并相邻的石子或石堆为一堆，代价为两者质量之和，最终要将所有石子合为一堆。由于合并顺序不同，总代价也不同，求最小总代价
2、对于区间 DP，通常用 $dp[i][j]$ 表示区间 $[i, j]$ 之间的价值最值，并用一个遍历的 $k$ 将 $[i, j]$ 划分为两个子区间进行状态转移
3、确定状态：令 $dp[i][j]$ 表示合并到区间 $[i, j]$ 所需的最小代价
4、确定转移：遍历 $k \in [i \to j)$，将区间 $[i, j]$ 分为 $[i, k]$ 和 $[k+1, j]$ 两个子区间。则 $dp[i][j]$ 可由合并到这两个子区间所需的最小价值加上这一次将这两个子区间合并所需的价值(即 $sum(i, j)$)转移而来，由于 $k$ 是在遍历的，所以还需要取最小值。因此得到 $dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum(i, j))$
5、初始化：$dp[i][i] = 0$ ，合并为长度为 $1$ 的区间不需要代价；此外，由于转移方程要与自身取 $min$，其余应初始化为 $\infty$
6、由于大区间的转移需要小区间的值，所以实现时应先算小区间。因此第一维应枚举区间长度 $len$，从长度为 $2$ 开始(长度为 $1$ 不需要转移且已初始化)；第二维则只需要枚举起点 $i$，终点即可表示为 $j = i + len - 1$代码实现
#include <bits/stdc++.h> using namespace std; const int N = 310; const int INF = 0x3f3f3f3f; int m[N], dp[N][N], prefix[N]; // dp[i][j] 表示合并到区间 [i, j] 的最小价值，prefix 为前缀和 void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> m[i]; // 处理前缀和 for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + m[i]; // 初始化 memset(dp, INF, sizeof(dp)); for (int i = 1; i <= n; i++) dp[i][i] = 0; // 枚举区间长度 k for (int len = 2; len <= n; len++) // 枚举起点 i，终点 j 即为 i + k - 1，注意 j 的初始化和自增 for (int i = 1, j = i + len - 1; j <= n; i++, j++) // 枚举中间点 k，范围 [i, j) for (int k = i; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefix[j] - prefix[i - 1]); cout << dp[1][n]; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
树形 DP-最大子树和
最大子树和
1、最大子树和：共 $T$ 组案例，每组给定一棵 $n$ 个节点的树($n \leq 10^5$)，再给出每个节点的权值 $w_i$(可能为负)，再给出 $n-1$ 组 $u, v$，表示存在连接节点 $u$ 和 $v$ 的边。规定连通块权值为块内所有节点权值之和(注意连通块可以只是子树中联通的部分节点，不一定需要完整的子树)，求出最大的连通块权值
2、对于树形 DP，通常用 $dp[i]$ 表示以 $i$ 为根的子树的价值最值。归属法：因为以 $i$ 为根可能有多棵子树，所以可以用子树根 $i$ 的值代表以它为根的一系列子树中的价值最值。需要注意，这样只是处理每棵子树的价值最值，最终根节点的最值不一定是整棵树最大的最值(如下例)。实现时大多数树形 DP 都采用 DFS 遍历
3、确定状态：令 $dp[i]$ 表示以 $i$ 为根的子树的最大权值和
4、确定转移：对于一棵以 $x$ 为根的树，其最大权值和首先一定要包含 $x$ 的价值(以 $x$ 为根，就不能把 $x$ 排出去)，可以以此作为初始化；找到更大的权值和的过程，可以看作是否选择子树，用 $y$ 遍历 $x$ 的子节点，考虑每一棵子树 $y$ 的最大权值和是否会让价值更大(如果为负，显然 $x$ 不包含子树 $y$ 更优)，则需要用 $max$ 比较当前权值和与加上子树 $y$ 的权值和。因此，转移方程为 $dp[x] = max(dp[x], dp[x] + dp[y])$
5、初始化：初始 $dp[i] = w[i]$ ，因为以 $i$ 为根至少包含它自己，并清空邻接表 $vec$(有多组数据，必须初始化)
6、由于大子树的转移需要小子树的值，所以实现时要先从小子树开始，使用 DFS 遍历，这样对于任意一棵子树，深度优先能使其需要的所有子树都递归地得到值。由于图是双向图，拓展时还需要记录父节点，防止重复处理。另外需要注意，处理的只是以 $i$ 为根的子树的最优权值和，处理后并不能说明根节点就是最大权值和(比如某一叶子节点为 $1000$，其余节点都为负)，所以输出时仍需要找最大值代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; vector<int> g[N]; int w[N], dp[N]; // dp[i] 表示以 i 为根的子树的最大权值和 // x 为当前节点，pre 为父节点 void DFS(int x, int pre) { // y 遍历所有子节点 for (auto &y : g[x]) { // 如果 y 等于父节点就跳过，防止双向图重复处理 if (y == pre) continue; DFS(y, x); // 深度优先，递归处理 dp[y] dp[x] = max(dp[x], dp[x] + dp[y]); // 状态转移 } } void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> w[i]; // 初始化 for (int i = 1; i <= n; i++) { dp[i] = w[i]; // dp[i] 一定至少包含它自己 g[i].clear(); } // 建图 for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } DFS(1, -1); // 此处调用父节点为 -1 相当于表示 1 看作根节点 // 输出最大的 dp cout << *max_element(dp + 1, dp + n + 1) << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0; }
存在 DP-砝码称重
砝码称重
1、砝码称重：有 $T$ 组样例($T \leq 100$)。对于每组样例，有 $n$ 个砝码，$m$ 个石子($n,m \leq 100$)，给出每个砝码的重量 $w_i$，再给出每个石子的重量 $x_i$。你有一个天平，对于每个给出的石子，如果能用天平砝码称出石子重量，输出 Yes，否则输出 No
2、对于存在 DP，通常用 bitset 表示所有可能的状态，bitset 由于也表示一个二进制数，可以通过位运算更方便地标记和转移
3、确定状态：令 $bs[i]$ 表示重量为 $i$ 能否被表示
4、确定转移：由题意，砝码可以不选或放在天平左右任意一侧，则其带来的价值对于当前称得总重量而言可能是 $0$ 或 $+w$ 或 $-w$ 。因此，转移方程为 $bs = bs \lor (bs << w) \lor (bs >> w)$：运用了位运算中的或运算，$bs$ 为当前所有可能的状态(也即不选的状态)，$bs << w$ 即将砝码放在右侧带来 $+w$ 的价值的所有状态，$bs << w$ 即将砝码放在左侧带来 $-w$ 的价值的所有状态，通过或运算将转移后所有可能的状态结合起来
5、初始化：初始 $bs[0] = true$，即重量为 $0$ 一定可以表示
6、但注意，状态转移过程中状态可能转移到负数(比如当前总重量 $-3$ 的情况)，但 $bs$ 不能下标为负(不能 $bs[-3] = true$)，所以需要一个偏移量 $F$ 用于表示基准下标 $0$，将 $bs[F]$ 看作 $bs[0]$ 以便表示负数的情况代码实现
#include <bits/stdc++.h> using namespace std; const int N = 2e4 + 10; const int F = 1e4 + 5; // F 为偏移量，表示基准下标 0 void solve() { int n, m; cin >> n >> m; bitset<N> bs; // bs[i] 表示重量为 i 能否被表示 bs[F] = true; // 看作 bs[0] = true for (int i = 1; i <= n; i++) { int w; cin >> w; bs = bs | (bs << w) | (bs >> w); } for (int i = 1; i <= m; i++) { int x; cin >> x; // 注意加上偏移量 F cout << (bs[F + x] ? "Yes" : "No") << '\n'; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0; }
计数 DP-台阶问题
台阶问题
1、台阶问题：有 $n$ 级台阶($n \leq 10^5$)，你一开始在底部($0$ 级)，每次可以向上迈 $1 \to k$ 级台阶($k \leq 100$)。输入 $n, k$，输出到达第 $n$ 级台阶有多少种不同方式，结果对 $10^5 + 3$ 取模
2、对于计数 DP，通常用 $dp[i]$ 表示到达结果 $i$的方案数量，转移方程通常类似递推
3、确定状态：令 $dp[i]$ 表示到达第 $i$ 级台阶的方案数量
4、确定转移：由于每次可以向上迈 $1 \to k$ 级台阶，所以当前级的可能性为向下 $1$ 级、向下 $2$ 级、…、向下 $k$ 级的方案数之和。因此，转移方程为 $dp[i] = (dp[i] + dp[i-j]) % P$，其中 $j$ 遍历地表示向下 $j$ 级(注意边界)。但实现时通常用 $j$ 直接表示需要转移的结果，其转移的范围为 $[max(0, j - k), i - 1]$ ，转移方程为 $dp[i] = (dp[i] + dp[j]) % P$
5、初始化：初始 $dp[0] = 1$ ，即到达 $0$ 级只有一种方案代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; const int P = 1e5 + 3; int dp[N]; // dp[i] 表示到达第 i 级的方案数 void solve() { int n, k; cin >> n >> k; dp[0] = 1; // 初始化 for (int i = 1; i <= n; i++) // 转移范围为 [max(0, i - k), i - 1]，注意边界 for (int j = max(0, i - k); j < i; j++) dp[i] = (dp[i] + dp[j]) % P; cout << dp[n] % P; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
计数 DP-小 A 点菜
小 A 点菜
1、小 A 点菜：有 $m$ 元钱($m \leq 10^4$)，有 $n$ 种菜品($n \leq 100$)。给出每种菜品的价格 $a_i$，输出正好把钱花光有多少种方案
2、确定状态：令 $dp[j]$ 表示正好花光 $j$ 元钱的方案数(实现上，类似一维 01 背包，若还原回 $dp[i][j]$ 则表示到第 $i$ 种菜为止正好花光 $j$ 元钱的方案数)
3、确定转移：先简单地讨论，对于 $dp[i][j]$ ，都有两种可能：选了当前菜 $dp[i][j] = dp[i-1][j]$ 和没选当前菜 $dp[i][j] = dp[i-1][j-a[i]]$ ，那么总的方案数即为两者之和。在此处通过类似一维 01 背包的方式处理(注意要从右向左处理)，则转移方程可化为 $dp[j] = dp[j] + dp[j-a[i]]$
4、初始化：初始$dp[0] = 1$ ，即花费 $0$ 元只有一种方案代码实现
#include <bits/stdc++.h> using namespace std; const int M = 1e5 + 10; const int N = 110; int dp[M]; // 正好花费 i 元的方案数 int a[N]; // 每种菜的价格 void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; dp[0] = 1; // 初始化 // 类似一维 01 背包的转移方式 for (int i = 1; i <= n; i++) for (int j = m; j - a[i] >= 0; j--) dp[j] = dp[j] + dp[j - a[i]]; cout << dp[m]; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
如果较为紧急，建议添加微信或QQ，并注明来意
评论系统可能加载较慢，请耐心等待或刷新重试