区间 DP

· · 个人记录

题单链接

区间动态规划（区间 DP）是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 f[i][j] 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f[i][j]=\max(f[i][k]+f[k+1][j]+cost)，cost 为将这两组元素合并起来的代价。

区间 DP 的特点：

  1. 合并：即将两个或多个部分进行整合，当然也可以反过来；

  2. 特征：能将问题分解为能两两合并的形式；

  3. 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

做法通常为：枚举区间长度，再枚举左端点，然后枚举区间断点进行转移。

先来一道题 P1880 石子合并

题目描述

有 n 堆石子，每堆分别有 a_i 个石子，将它们绕圆形操场摆放，现在要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆石子数，记为该次合并的得分。

求出将 n 堆石子合并成 1 堆的最小得分和最大得分。

样例组

样例解释

得分最小：4 5 9 4 -> 8 5 9 -> 13 9 -> 22

得分最大：4 5 9 4 -> 4 14 4 -> 18 4 -> 22

。 。 。 。 。 ### Solution 考虑石子在链上的情况。 设 $\mathrm{dpmin}[i][j]$ 为将第 $i$ 堆石子到第 $j$ 堆石子合并成 $1$ 堆的最小得分，$\mathrm{dpmax}[i][j]$ 为将第 $i$ 堆石子到第 $j$ 堆石子合并成 $1$ 堆的最大得分。易得 $\mathrm{dpmin}[i][i]=\mathrm{dpmax}[i][i]=a_i$。 首先枚举区间长度（从 $2$ 到 $n$，因为长度为 $1$ 的区间已经处理完毕），然后枚举区间左端点，得到区间右端点。然后枚举区间断点（即枚举答案如何转移）。 设第一堆石子到第 $i$ 堆石子的石子数总和为 $sum[i]$，则容易得到状态转移方程为： $$\mathrm{dpmin}[i][j]=\min(\mathrm{dpmin}[i][k]+\mathrm{dpmin}[k+1][j]+\mathrm{sum}[j]-\mathrm{sum}[i-1])$$ $$\mathrm{dpmax}[i][j]=\max(\mathrm{dpmax}[i][k]+\mathrm{dpmax}[k+1][j]+\mathrm{sum}[j]-\mathrm{sum}[i-1])$$ 对于环的问题，可以“断环为链”。 我们将这条链延长两倍，变成 $2\times n$ 堆，其中第 $i$ 堆与第 $n+i$ 堆相同，用动态规划求解后，取 $\mathrm{dp}[1][n],\ \mathrm{dp}[2][n+1],\ \cdots,\ \mathrm{dp}[i][n+i-1],\ \cdots,\ \mathrm{dp}[n-1][2n-1]$ 中的最优值，即为最后的答案。 时间复杂度 $\mathcal{O}(n^3)$，空间复杂度 $\mathcal{O}(n^2)$。 ```cpp #include <bits/stdc++.h> using namespace std; const int inf = 0x7FFFFFFF; int n, a[410], sum[410], dp1[410][410], dp2[410][410]; int ans1 = inf, ans2 = -inf; int main() { cin >> n; memset(dp1, 0x3f, sizeof(dp1)); memset(dp2, 0xc0, sizeof(dp2)); for (int i = 1; i <= n; i++){ cin >> a[i]; sum[i] = sum[i - 1] + a[i]; dp1[i][i] = dp2[i][i] = 0; } for (int i = n + 1; i < n * 2; i++) { a[i] = a[i - n]; sum[i] = sum[i - 1] + a[i]; dp1[i][i] = dp2[i][i] = 0; } for (int l = 2; l <= n; l++) { for (int i = 1; i <= 2 * n - l + 1; i++) { int j = l + i - 1; for (int k = i; k < j; k++) { dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + sum[j] - sum[i - 1]); dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]); } } } for (int i = 0; i < n; i++) { ans1 = min(ans1, dp1[i + 1][n + i]); ans2 = max(ans2, dp2[i + 1][n + i]); } cout << ans1 << endl << ans2 << endl; return 0; } ``` ------------ ### [P2858 Treats For The Cows](https://www.luogu.com.cn/problem/P2858) ### 题目描述 约翰购置了 $n$ 份零食来卖给奶牛们，每天约翰售出一份零食。这些零食有一下特性： - 零食按照 $1, \ 2,\ \cdots,\ n$ 编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个； - 这些零食储存得越久就越好吃，这样约翰就可以把它们卖出更高的价钱； - 每份零食的初始价值不一定相同。约翰进货时，第 $i$ 份零食的初始价值为 $v_i$； - 第 $i$ 份零食如果在被买进后的第 $a$ 天出售，则它的售价为 $v_i\times a$。 $v_i$ 是从盒子顶端往下的第 $i$ 份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。 ### 样例组 ![](https://cdn.luogu.com.cn/upload/image_hosting/mak55082.png) ### 样例解释 约翰以卖出第 $1$ 份、第 $5$ 份、第 $2$ 份、第 $3$ 份、第 $4$ 份零食的顺序卖出零食，这样他能获得 $1\times1+2\times2+3\times3+1\times4+5\times5=43$ 元钱。 $1\leq n\leq2000,\ 1\leq v_i\leq1000$。 。 。 。 。 。 ### Solution 设 $\mathrm{dp}[i][j]$ 为卖出第 $i$ 份零食到第 $j$ 份零食最多能获得的钱。 这道题和上一道题差别不大，但是可以直接省去枚举区间断点的步骤，因为新加入的只可能是两端的零食。 **边界情况：$\mathrm{dp}[i][i]=v_i\times n$ ！！！** 时间复杂度 $\mathcal{O}(n^2)$，空间复杂度 $\mathcal{O}(n^2)$。 ```cpp #include <bits/stdc++.h> using namespace std; const int inf = 0x7FFFFFFF; int n, v[2010], dp[2010][2010]; int main() { cin >> n; memset(dp, 0xc0, sizeof(dp)); for (int i = 1; i <= n; i++) { cin >> v[i]; dp[i][i] = v[i] * n; } for (int l = 2; l <= n; l++) { for (int i = 1; i <= n - l + 1; i++) { int j = l + i - 1; dp[i][j] = max(dp[i + 1][j] + v[i] * (n - l + 1), dp[i][j - 1] + v[j] * (n - l + 1)); } } cout << dp[1][n]; return 0; } ``` ------------ ### [P1063 能量项链](https://www.luogu.com.cn/problem/P1063) ### 题目描述 在 `Mars` 星球上，每个人都佩戴着一串能量项链。在项链上有 $n$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记代表着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。相邻两颗珠子可以聚合成一颗珠子，并且产生能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $p$，则聚合后释放的能量为 $m\times r\times p$，新产生的珠子头标记为 $m$，尾标记为 $p$。 例如：设 $n=4$，$4$ 颗珠子的头标记和尾标记分别为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\otimes$ 表示两颗珠子的聚合操作，$(j\otimes k)$ 表示第 $j,\ k$ 两颗珠子聚合后释放的能量。则第 $4$、$1$ 两颗珠子聚合后释放的能量为： $$(4\otimes1)=10\times2\times3=60$$ 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为： $$((4\otimes1)\otimes2)\otimes3=10\times2\times3+10\times3\times5+10\times5\times10=710$$ 请你设计一个聚合顺序，使一串项链释放出的总能量最大。 ### 样例组 ![](https://cdn.luogu.com.cn/upload/image_hosting/2pdmxtal.png) $4\leq n\leq100$，所有的数均不超过 $1000$，答案不大于 $2.1\times10^9$。 。 。 。 。 。 ### Solution 设 $\mathrm{dp}[i][j]$ 表示第 $i$ 到第 $j$ 颗珠子聚合的最大能量，$a[i].h$ 表示第 $i$ 颗珠子的头标记，$a[i].t$ 表示第 $j$ 颗珠子的尾标记。 可以先枚举区间长度（已聚合珠子个数），再枚举左端点，再在区间内枚举断点。 状态转移方程：$\mathrm{dp}[i][j]=\max(\mathrm{dp}[i][k]+\mathrm{dp}[k+1][j]+a[i].h\times a[j].t\times a[k].t)$。 因为珠子形成了一个环，所以可以断环为链。 时间复杂度 $\mathcal{O}(n^3)$，空间复杂度 $\mathcal{O}(n^2)$。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int inf = 0x7FFFFFFF; struct node { int h, t; }a[210]; int n, dp[210][210], ans = 0; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i].h); a[i - 1].t = a[i].h; } a[n].t = a[1].h; for (int i = n + 1; i < n * 2; i++) { a[i] = a[i - n]; } for (int l = 2; l <= n; l++) { for (int i = 1; i <= n * 2 - l; i++) { int j = i + l - 1; for (int k = i; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i].h * a[k].t * a[j].t); } } } for (int i = 1; i <= n; i++) { ans = max(ans, dp[i][n + i - 1]); } printf("%d\n", ans); return 0; } ``` ------------ ### [P4170 涂色](https://www.luogu.com.cn/problem/P4170) ### 题目描述 你有一条长度为 $n$ 的木板，没有涂过任何颜色。每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。 你需要把木板涂成一个涂色目标，请输出最少的涂色次数。 ### 样例组 ![](https://cdn.luogu.com.cn/upload/image_hosting/iffri5or.png) ### 样例解释 对于样例 #2，可行的涂色步骤如下： 1. $\texttt{RRRRR}
  1. \texttt{RGGGR}
  2. \texttt{RGBGR}

可以证明没有涂色次数更少的方案。

。 。 。 。 。 ### Solution 设字符串 $s$ 为目标，$\mathrm{dp}[i][j]$ 表示将区间 $[i,j]$ 涂成目标颜色的最少次数。 当 $i=j$ 时，只需要涂色 $1$ 次，所以 $\mathrm{dp}[i][j]=1$。 当 $i\neq j$ 且 $s_i=s_j$ 时，在涂上一个区间（即 $[i+1,j]$ 和 $[i,j-1]$）时可以直接涂上，所以 $\mathrm{dp}[i][j]=\min(\mathrm{dp}[i+1][j],\mathrm{dp}[i][j-1])$。 当 $s_i\neq s_j$ 时，可以把区间分成两部分完成，一部分包含 $i$，一部分包含 $j$，将两个区间的次数加和即可。所以 $\mathrm{dp}[i][j]=\min(\mathrm{dp}[i][j],\mathrm{dp}[i][k]+\mathrm{dp}[k+1][j])$。 整合一下，转移方程如下： $$\begin{cases}i=j,&\mathrm{dp}[i][j]=1\\i\neq j,s_i=s_j,&\mathrm{dp}[i][j]=\min(\mathrm{dp}[i+1][j],\mathrm{dp}[i][j-1])\\s_i\neq s_j,&\mathrm{dp}[i][j]=\min(\mathrm{dp}[i][j],\mathrm{dp}[i][k]+\mathrm{dp}[k+1][j])\end{cases}$$ 时间复杂度 $\mathcal{O}(n^3)$，空间复杂度 $\mathcal{O}(n^2)$。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int inf = 0x7FFFFFFF; char a[60]; int n, dp[60][60]; int main() { memset(dp, 0x3f, sizeof(dp)); scanf("%s", a); n = strlen(a); for (int i = 1; i <= n; i++) { dp[i][i] = 1; } for (int l = 2; l <= n; l++) { for (int i = 1; i <= n - l + 1; i++) { int j = i + l - 1; if (a[i - 1] == a[j - 1]) { dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]); } else { for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } } printf("%d\n", dp[1][n]); return 0; } ``` ------------ ### [P1220 关路灯](https://www.luogu.com.cn/problem/P1220) ### 题目描述 一个村子里有 $n$ 盏路灯，老张每天早上都要去关路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，。他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他首先关掉自己所在位置的灯，然后他可以向左或向右去关灯，并且在过程中也可以随时掉头。 已知老张走路的速度是 $1\mathrm{m/s}$，每个路灯的位置（一个正整数，单位 $\mathrm{m}$），每个路灯的功率（一个正整数，单位 $\mathrm{W}$（瓦））。老张关灯的时间忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了），输出最后的功耗（单位 $\mathrm{J}$，$1\mathrm{J}=1\mathrm{W}\times1\mathrm{s}$）。 $1\leq n\leq50,\ 1\leq c\leq n$。 。 。 。 。 。 ### Solution **先**设 $\mathrm{dp}[i][j]$ 表示关掉第 $i$ 到第 $j$ 盏灯的最小功耗。 > 但是不知道老张在哪，没法转移。 所以设 $\mathrm{dp}[i][j][0/1]$ 表示关掉第 $i$ 到第 $j$ 盏灯的最小功耗，其中 $\mathrm{dp}[i][j][0]$ 表示老张在第 $i$ 盏路灯处，另外一种情况同理。 状态转移方程如下： $$\mathrm{dp}[i][j][0]=\min(\mathrm{dp}[i+1][j][0]+\mathrm{cal}() ,\mathrm{dp}[i+1][j][1]+\mathrm{cal}())$$ $$\mathrm{dp}[i][j][1]=\min(\mathrm{dp}[i][j-1][0]+\mathrm{cal}(),\mathrm{dp}[i][j-1][1]+\mathrm{cal}())$$ 现在我们来看 $\mathrm{cal}$： $\mathrm{cal}$ 指的就是计上一个区间转移过来时没关的路灯消耗的电力。 设 $sum[i]$ 表示功率的前缀和，$a[i].w$ 表示第 $i$ 盏路灯的位置。 则 $\mathrm{cal}$ 的代码如下： ```cpp int cal(int i, int j, int l, int r) { return (a[j].w - a[i].w) * (sum[l] + sum[n] - sum[r - 1]); //a[j].w - a[i].w 表示老张要走的路程（也是时间，因为速度是1米每秒） //sum[l] + sum[n] - sum[r - 1] 表示每一秒花费的电力 } ``` 于是完整的状态转移方程如下： $$\mathrm{dp}[i][j][0]=\min(\mathrm{dp}[i+1][j][0]+\mathrm{cal}(i,i+1,i,j+1) ,\mathrm{dp}[i+1][j][1]+\mathrm{cal}(i,j,i,j+1))$$ $$\mathrm{dp}[i][j][1]=\min(\mathrm{dp}[i][j-1][0]+\mathrm{cal}(i,j,i-1,j),\mathrm{dp}[i][j-1][1]+\mathrm{cal}(j-1,j,i-1,j))$$ 空间复杂度 $\mathcal{O}(n^2)$，时间复杂度 $\mathcal{O}(n^2) 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x7FFFFFFF;
const LL Linf = 0x7FFFFFFFFFFFFFFF;
struct node {
    int w, p;
} a[60];
int n, c, sum[60];
int dp[60][60][2];
inline int cal(int i, int j, int l, int r) {
    return (a[j].w - a[i].w) * (sum[l] - sum[r - 1] + sum[n]);
}
int main() {
    memset(dp, 0x3f, sizeof(dp));
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].w, &a[i].p);
        sum[i] = sum[i - 1] + a[i].p;
    }
    dp[c][c][0] = dp[c][c][1] = 0;
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            dp[i][j][0] = min(dp[i + 1][j][0] + cal(i, i + 1, i, j + 1), dp[i + 1][j][1] + cal(i, j, i, j + 1));
            dp[i][j][1] = min(dp[i][j - 1][0] + cal(i, j, i - 1, j), dp[i][j - 1][1] + cal(j - 1, j, i - 1, j));
        }
    }
    printf("%d\n", min(dp[1][n][0], dp[1][n][1]));
    return 0;
}

参考资料

  1. 洛谷日报
  2. OI Wiki
  3. 计蒜客