区间DP总结

2.1.3 区间DP

2.1.3.1 基本概念

​ 区间DP，顾名思义是在区间上DP，它以“区间长度”作为DP的“阶段”，使用两个坐标(区间的左、右端点)描述每个维度。它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。

2.1.3.2 核心思路

​ 既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度 $len$ 为每次分割成的小区间长度$($由短到长不断合并$)$，内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

下面给出代码$:$

for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;  //初始值
}
for (int i = 2; i <= n; i++) {              //区间长度
    for (int l = 1; l <= n - i + 1; l++) {  //左端点
        int r = l + i - 1;                  //右端点
        for (int j = l; j < r; j++) {       //划分
            dp[l][r] = min(dp[l][r], dp[l][j] + dp[j + 1][r] + w[l][r]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.1.3.3 石子合并

​ 有$n$堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？

假设只有2堆石子，显然只有1种合并方案。

​ 不管怎么合并，总之最后总会归结为2堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。

m [ i ] [ j ] = { 0 i = j min ⁡ ( m [ i ] [ k ] + m [ k + 1 ] [ j ] ) + w [ i ] [ j ] i < j m[i][j]=

$$\begin{cases}0&i=j\\ \min(m[i][k]+m[k+1][j])+w[i][j]&i<j\end{cases}$$ m[i][j]={0min(m[i][k]+m[k+1][j])+w[i][j]​i=ji<j​

预处理 $w[i][j]:$
先算出前缀和 $s[i]$ ，然后$w[i][j]=s[j]–s[i-1]$
因此，$w[i][j]$可以不事先存放，在DP​时直接 $O(1)$ 计算。

#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 5;
int a[M];
long long sum[M], dp[M][M];
int n;
int main() {
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) dp[i][i] = 0;
    for (int i = 2; i <= n; i++) {
        for (int l = 1; l <= n - i + 1; l++) {
            int r = l + i - 1;
            for (int j = l; j < r; j++) {
                dp[l][r] = min(dp[l][r], dp[l][j] + dp[j + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    }
    printf("%lld", dp[1][n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.1.3.4 戳西瓜

​ 有 n 个西瓜，编号为 $0$ 到 $n-1$ ，每个西瓜上都标有一个数字，这些数字存在数组 $nums$ 中。现在要求你戳破所有的西瓜。每当你戳破一个西瓜$i$时，你可以获得 $nums[left]\ast nums[i]\ast nums[right]$ 个硬币。这里的 $left$ 和 $right$ 代表和 $i$ 相邻的两个西瓜的序号。注意当你戳破了西瓜 $i$ 后，西瓜 $left$ 和西瓜 $right$ 就变成了相邻的西瓜。求所能获得硬币的最大数量。

数据范围与提示$:$你可以假设 $nums[-1]=nums[n]=1$ ，但注意它们不是真实存在的西瓜，所以并不能被戳破。

假设 $dp[i][j]$ 表示开区间 $(i,j)$ 内你能拿得最多的硬币。

那么在这个情况下$(i,j)$开区间得到的金币可以由 $dp[i][j]$ 和 $dp[k][j]$ 进行转移，如果你此刻选择戳爆 $K$ ，那么你得到的金币数量就是$dp[i][k]+nums[i]\ast nums[k]\ast nums[j]+dp[k][j]$

#include <bits/stdc++.h>
using namespace std;
const int M = 505;
int a[M], dp[M][M];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = a[n + 1] = 1;
    int m = n + 2;
    for (int i = 2; i < m; i++) {
        for (int l = 0; l + i < m; l++) {
            int r = l + i;
            for (int j = l + 1; j < r; j++)
                dp[l][r] = max(dp[l][r], dp[l][j] + dp[j][r] + a[l] * a[j] * a[r]);
        }
    }
    printf("%d", dp[0][m - 1]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.1.3.5 「COCI 2010.03.06」ZUMA

Mirko 将 $n$ 颗弹子排成一排，依次编号为 $1...N$。 号弹子的颜色为 $c[i]$ 。他发现，如果他触摸 $\ge k$ 颗连续的弹子，且这些弹子的颜色相同，魔法会使这些弹子消失；此后，这 $k$ 颗弹子前面的弹子便与这 $k$ 颗弹子后面的弹子相邻。

Mirko 家里有很多弹子，他想在这 颗弹子之间（也可以在开头的弹子前面或末尾的弹子后面）插入尽可能少的弹子，使得这 $k$ 颗弹子+插入的所有弹子消失。

这到题略微有一点变化。

我们设 $dp[i][j][sum]$ 表示消除区间 $[i,j]$ 在左边添加了 $sum$ 个珠子的总添加珠子数。

答案就是 $dp[1][n][0]$ 。

转移方程如下$:$

1. 当 $sum<k-1$ (不能消)时再加一个，即 $dp[i][j][sum]=min(f[i][j][sum],f[i][j][sum+1]+1)$
2. 当 $sum=k-1$ 时直接消掉，即 $dp[i][j][sum]=dp[i+1][j][0]$
3. 当 $i$ 和 $i+1$ 的颜色相同时，可以把 $i$ 加到 $i+1$ 的整体中，即 $dp[i][j][sum]=dp[i+1][j][sum+1]$

#include <bits/stdc++.h>
using namespace std;

int a[105], dp[105][105][105];
int n, k;

int dfs(int l, int r, int sum) {
    if (l > r)  //边界
        return 0;
    if (dp[l][r][sum] != -1)  //记忆化
        return dp[l][r][sum];
    int ans = 0x3f3f3f3f;
    dp[l][r][sum] = 0x3f3f3f3f;
    if (sum < k - 1)  //第一种情况
        ans = min(ans, dfs(l, r, sum + 1) + 1);
    else if (sum == k - 1)  //直接消掉
        ans = dfs(l + 1, r, 0);
    for (int i = l + 1; i <= r; i++)
        if (a[i] == a[l])  //加入后面形成一个整体
            ans = min(ans, dfs(l + 1, i - 1, 0) + dfs(i, r, min(k - 1, sum + 1)));
    dp[l][r][sum] = ans;
    return ans;
}

int main() {
    scanf("%d %d", &n, &k);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    dfs(1, n, 0);
    printf("%d", dp[1][n][0]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32