序列 DP
一般序列 DP 核心思想：将序列的前 \(i\) 个数的状态用一个更简单的形式表示出，并且体现出这些状态对后续的影响。
题目
ABC 267D
给定一个序列 \(a\)，找到一个长度为 \(m\) 的子序列 \(b\)，使得 \(\sum b_i × i\) 最大。
\(n, m \le 2 × 10^3\)。
状态：\(f(i, j)\)：前 \(i\) 个数，选 \(j\) 个数的最大和；
转移：\(f(i, j) = \max(f(i - 1, j), f(i - 1, j - 1) + a_i \times j)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2010;
int n, m;
ll a[N], dp[N][N];
int main() {
memset(dp, 128, sizeof dp);
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
dp[i][0] = 0;
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= min(i, m); ++ j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + 1ll * j * a[i]);
}
}
printf("%lld\n", dp[n][m]);
return 0;
}
B3637 最长上升子序列
给定一个序列，求它的最长上升子序列。\(n \le 5000\)
状态：\(dp_i\)：最长上升子序列中第 \(i\) 个元素（是什么）；
转移：如果 新元素 \(a\) 大于 \(dp_i\)，则 \(dp_{i + 1} = a\)，否则，二分出第一个大于等于 \(a\) 的前一个位置，替换上它。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int n;
int y[100], dp[100];
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
y[i] = read();
}
dp[1] = y[1];
int cnt = 1;
for (int i = 2; i <= n; ++ i) {
if (y[i] > dp[cnt]) {
dp[++ cnt] = y[i];
}
else {
int p = lower_bound(dp + 1, dp + cnt + 1, y[i]) - dp;
dp[p] = y[i];
}
}
printf("%d\n", cnt);
return 0;
}
P1439 【模板】最长公共子序列
给定两个 \(1, 2, 3 \cdots n\) 的序列 \(a, b\)，求它们的最长公共子序列。
\(n \le 10^5\)。
- 朴素做法 \(O_{n^2}\)：
状态：\(dp(i, j)\)：第一个串的前 \(i\) 位，第二个串的前 \(j\) 位的 LCS 的长度；
如果当前的 \(a_i = b_j\) 相同（即是有新的公共元素） 那么dp[i][j]=max(dp[i][j],dp[i−1][j−1])+1;；如果不相同，即无法更新公共元素，考虑继承：dp[i][j]=max(dp[i−1][j],dp[i][j−1])。
#include<iostream>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2010;
int n, m;
int dp[N][N], a1[N], a2[N];
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
a1[i] = read();
}
for (int i = 1; i <= m; ++ i) {
a2[i] = read();
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (a1[i] == a2[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
printf("%d\n", dp[n][m]);
return 0;
}
- 针对本题的 \(O_{n \log n}\) 做法。
我们将 \(b\) 中的元素改为该元素在 \(a\) 中的位置，如果有一段位置是单调递增的，则这一段就是公共的子序列，我们再进行 DP。
状态：\(dp_i\)：最长公共子序列的第 \(i\) 个元素（是什么）；
转移：如果当前的 \(b_i\) 大于 \(dp_{last}\)，则 \(dp_{last + 1} = b_i\)，否则，二分找出大于等于 \(b_i\) 的前一个位置，替换。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int n;
ll a[N], b[N], l[N], dp[N];
int main() {
n = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
l[a[i]] = i;
}
for (int i = 1; i <= n; ++i) {
b[i] = read();
b[i] = l[b[i]];
}
int len = 1, s;
dp[1] = b[1];
for (int i = 2; i <= n; ++i) {
if (b[i] > dp[len]) {
len ++;
dp[len] = b[i];
}
else {
s = lower_bound(dp + 1, dp + len + 1, b[i]) - dp;
dp[s] = b[i];
}
}
printf("%d", len);
return 0;
}
区间 DP
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
令状态 \(f(i,j)\) 表示将下标位置 \(i\) 到 \(j\) 的所有元素合并能获得的价值的最大值，那么 \(f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}\)，\(cost\) 为将这两组元素合并起来的代价。
题目
P1775 石子合并
有 \(n\) 堆石子，每堆石子有编号有重量，现在要将它们合并成一堆，只能合并相邻的两堆石子，且代价为两堆石子的重量和，求最小代价。\(n \le 300\)
状态：\(dp(i, j)\)：合并 \(\left[ i, j \right]\) 的石子的最小代价。
转移：\(dp(i, j) = \min_{k = i}^{j - 1} \left\{ dp(i, k) + dp(k + 1, j) + cost(i, j) \right\}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 410;
int n;
int a[N], dp[N][N], s[N];
int main() {
memset(dp, 0x3f, sizeof dp);
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
dp[i][i] = 0;
s[i] = s[i - 1] + a[i];
}
for (int l = 2; l <= n; ++ l) {
for (int i = 1; i + l - 1 <= n; ++ i) {
int j = i + l - 1;
for (int k = i; k < j; ++ k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
}
}
}
printf("%d\n", dp[1][n]);
return 0;
}
P4170 [CQOI2007]涂色
有一条长度为 \(5\) 的木板，初始时没有涂过任何颜色。每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。用尽量少的涂色次数达到目标。\(n \le 50\)
状态：\(dp(i, j)\) 将木板 \(\left[ i, j \right]\) 涂成目标颜色的最小涂色次数。
转移：
如果 \(color_j = color_{j - 1}\)，则 \(dp(i, j) = dp(i - 1, j)\)；
否则 \(dp(i, j) = \min_{k = i}^{j - 1} \left \{ dp(i, k) + dp(k + 1, j) \right \}\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 100;
int n;
char s[N];
ll dp[N][N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; ++ i)
dp[i][i] = 1;
for (int l = 1; l < n; ++ l) {
for (int i = 1; i + l <= n; ++ i) {
int j = i + l;
if (s[i] == s[j]) {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
} else {
for (int k = i; k < j; ++ k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
printf("%lld\n", dp[1][n]);
return 0;
}
P1220 关路灯
在一条路线上安装了 \(n\) 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。现在已知老张走的速度为 \(1m/s\)，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。问：怎样最省电？\(n \le 50\)
考虑对于状态的设计，关掉一段区间的灯，需要存下左右端点，需要两维，对于关掉区间 \(\left [ l, r \right ]\)，最后一次只可能是关掉 \(l\) 位置的灯或者 \(r\) 位置的灯，即最后停留的位置有最左端与最右端两种，且对答案有影响，再加一维来存这两种情况。
状态：\(dp(i, j, 0/1)\)
转移：\(dp(i, j, 0) = \min(dp(i + 1, j, 0) + cost_1, dp(i + 1, j, 1) + cost_2\)),
\(dp(i, j, 1) = \min(dp(i, j - 1, 0) + cost_1, dp(i, j - 1, 1) + cost_2)\)，
初始化：\(dp(c, c, 0) = 0, dp(c, c, 1) = 0\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int f = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
f |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return f ? ~x + 1 : x;
}
const int N = 110;
int n, c, sum, ans;
int a[N], w[N], s[N];
int dp[N][N][2];
bool b[N];
int main() {
n = read(), c = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read(), w[i] = read();
s[i] = s[i - 1] + w[i];
}
memset(dp, 0x3f, sizeof dp);
dp[c][c][0] = 0;
dp[c][c][1] = 0;
for (int j = c; j <= n; ++ j) {
for (int i = j - 1; i >= 1; -- i) {
dp[i][j][0] = min(dp[i + 1][j][0] + (a[i + 1] - a[i]) * (s[n] + s[i] - s[j]), dp[i + 1][j][1] + (a[j] - a[i]) * (s[n] + s[i] - s[j]));
dp[i][j][1] = min(dp[i][j - 1][0] + (a[j] - a[i]) * (s[n] + s[i - 1] - s[j - 1]), dp[i][j - 1][1] + (a[j] - a[j - 1]) * (s[n] + s[i - 1] - s[j - 1]));
}
}
ans = min(dp[1][n][0], dp[1][n][1]);
printf("%d", ans);
return 0;
}
P3146 [USACO16OPEN]248 G
给定一个 \(1 \times n\) 的地图，在里面玩 2048，每次可以合并相邻两个（数值范围 \(1 \sim 40\)），问序列中出现的最大数字的值最大是多少。注意合并后的数值并非加倍而是 \(+1\)，例如 \(2\) 与 \(2\) 合并后的数值为 \(3\)，\(2 \le n \le 248\)
这里要考虑 2048 的游戏规则，即只有两个相邻的数相等才能合。
状态：\(dp(i, j)\)：合并区间 \(\left [ i, j \right ]\) 后的最大数值。
转移：\(dp(i, j) = \max(dp(i, j), dp(k + 1, j) + 1)\)，条件：\(dp(i, k) = dp(k + 1, j)\)，这里要注意，如果 \(dp(k + 1, j)\) 为 \(0\)，说明这段区间没被更新到，因此答案也不可能为 \(1\)，应该为 \(0\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 510;
int n, ans;
int a[N];
int dp[N][N];
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
dp[i][i] = a[i];
}
for (int len = 1; len <= n - 1; ++ len)
for (int i = 1; i <= n - len; ++ i) {
int j = i + len;
for (int k = i; k < j; ++ k) {
if (dp[k + 1][j] > 0 && dp[i][k] == dp[k + 1][j]) {
dp[i][j] = max(dp[i][j], dp[k + 1][j] + 1);
ans = max(ans, dp[k + 1][j] + 1);
}
}
}
printf("%d", ans);
return 0;
}
P3205 [HNOI2010]合唱队
合唱队一共 \(n\) 个人，第 \(i\) 个人的身高为 \(h_i\) 米（\(1000 \le h_i \le 2000\)），并已知任何两个人的身高都不同。假定最终排出的队形是 \(A\) 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中： 第一个人直接插入空的当前队形中；对从第二个人开始的每个人，如果他比前面那个人高（\(h\) 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（\(h\) 较小），那么将他插入当前队形的最左边。当 \(n\) 个人全部插入当前队形后便获得最终排出的队形。答案要对 \(19650827\) 取模，\(n \le 1000\)，\(1000 \le h_i \le 2000\)。
这道题与关路灯那道题差不多，在状态设计上要考虑上一个被插入的人是插入的左边还是右边。
状态：\(dp(i, j, 0/1)\)：区间 \(\left[ i, j \right]\) 中，最后一个人被插入了 \(0\) 左边 / \(1\) 右边。
转移：
如果 \(a_i < a_j\)，那么 \(dp(i, j, 0) = dp(i, j, 0) + dp(i + 1, j, 1), dp(i, j, 1) = dp(i, j, 1) + dp(i, j - 1, 0)\)，
如果 \(a_i < a_{i + 1}\)，那么 \(dp(i, j, 0) = dp(i, j, 0) + dp(i + 1, j, 0)\)，
如果 \(a_j > a_{j - 1}\)，那么 \(dp(i, j, 1) = dp(i, j, 1) + dp(i, j - 1, 1)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2010;
const int mod = 19650827;
int dp[N][N][2], a[N];
int main() {
int n;
n = read();
for (int i = 1; i <= n; ++ i)
a[i] = read();
for (int i = 1; i <= n; ++ i)
dp[i][i][0] = 1;
for (int i = n - 1; i >= 1; -- i) {
for (int j = i + 1; j <= n; ++ j) {
if (a[i] < a[j]) {
dp[i][j][0] += dp[i + 1][j][1];
dp[i][j][1] += dp[i][j - 1][0];
dp[i][j][0] %= mod;
dp[i][j][1] %= mod;
}
if (a[i] < a[i + 1]) {
dp[i][j][0] += dp[i + 1][j][0];
dp[i][j][0] %= mod;
}
if (a[j] > a[j - 1]) {
dp[i][j][1] += dp[i][j - 1][1];
dp[i][j][1] %= mod;
}
}
}
printf("%d", (dp[1][n][0] + dp[1][n][1]) % mod);
return 0;
}
环状 DP
在环上的 DP，基本方法就是断环为链，然后把它作为区间 DP 或 序列 DP 去做。作为区间 DP 做时有一个小技巧就是将 这个链复制两遍，以防止首位的一些非法情况被我们计算。
P1880 [NOI1995] 石子合并
石子合并，但是，是在环上。\(n \le 100\)
断环为链，复制两遍这条链转化为区间 DP。
状态：\(f1(i, j)\)：区间 \(\left[ i, j \right ]\) 的最大得分，\(f2(i, j)\)：区间 \(\left[ i, j \right ]\) 的最小得分。
转移：\(f1(i, j) = \max_{k = i}^{j - 1}\{f1(i, j), f1(i, k) + f1(k + 1, j) + cost\}\)
\(f2(i, j) = \min_{k = i}^{j - 1}\{f2(i, j), f2(i, k) + f2(k + 1, j) + cost\}\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
ll r[600], g[600];
ll f1[600][600], f2[600][600];
int main() {
int n;
n = read();
for (int i = 1; i <= n; ++i) {
r[i] = read();
r[i + n] = r[i];
g[i] = g[i - 1] + r[i];
f1[i][i] = f2[i][i] = 0;
}
for (int i = n + 1; i <= 2 * n; ++i) {
f2[i][i] = 0;
g[i] = g[i - 1] + r[i];
}
for (int l = 1; l < n; ++l) {
for (int i = 1, j = i + l; i < n * 2 && j <= n * 2; ++i, j = i + l) {
f2[i][j] = 100000000;
for (int k = i; k < j; ++k) {
f1[i][j] = max(f1[i][j], f1[i][k] + f1[k + 1][j] + g[j] - g[i - 1]);
f2[i][j] = min(f2[i][j], f2[i][k] + f2[k + 1][j] + g[j] - g[i - 1]);
}
}
}
ll maxn = 0, minn = 1e18;
for (int i = 1; i <= n; ++i) {
maxn = max(maxn, f1[i][i + n - 1]);
minn = min(minn, f2[i][i + n - 1]);
}
printf("%lld\n%lld", minn, maxn);
return 0;
}
P1063 [NOIP2006 提高组] 能量项链
给定一个有 \(n\) 个珠子的项链，每个珠子有头标记和尾标记，相邻两个珠子，前一个珠子的尾标记等于后一个珠子的头标记，只有相邻的两个柱子能合并成一个，并产生能量，能量为 \(前一颗珠子的头标记 \times 后一颗珠子的头标记 \times 后一颗珠子的尾标记\)，合并后的新珠子，头标记等于前一颗珠子的头标记，尾标记等于后一颗珠子的尾标记。求最大能量。\(4 \le n \le 400\)
很经典的环形 DP 题。
状态：\(dp(i, j)\)： 合并区间 \(\left[ i, j \right]\) 释放的最大能量。
转移：\(dp(i, j) = \max_{k = i}^{j - 1}\{dp(i, k) + dp(k + 1, j) + a_i \times a_{k + 1} \times a_{j + 1} \}\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int n;
ll a[300], f[300][300];
ll maxn;
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
a[i + n] = a[i];
}
for (int i = 2; i < 2 * n; ++ i)
for (int j = i - 1; i - j < n && j >= 1; -- j)
for (int k = j; k < i; ++ k) {
f[j][i] = max(f[j][i], a[j] * a[k + 1] * a[i + 1] + f[j][k] + f[k + 1][i]);
if (f[j][i] > maxn) maxn = f[j][i];
}
printf("%lld", maxn);
return 0;
}