跳转至

区间dp

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

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

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

例题

P1880 [NOI1995] 石子合并 - 洛谷

可以先将圆环扩成一条链。

定义 \(dp_{i,j,k}\) 为第 \(i\) 堆石子到第 \(j\) 堆石子的最小/大代价，\(sum_i\) 表示前 \(i\) 堆石子的质量和。

从小到大枚举长度进行区间dp即可。

代码
C++
 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int dp[305][305][2], a[305], sum[305];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1 ; i <= 2 * n ; i++) {
        for (int j = i ; j <= 2 * n ; j++) {
            dp[i][j][0] = 1e9;
            dp[i][j][1] = -1e9;
        }
        dp[i][i][0] = 0;
        dp[i][i][1] = 0;
    }
    for (int i = 1 ; i <= 2 * n ; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    for (int len = 2 ; len <= 2 * n ; len++) {
        for (int L = 1 ; L + len - 1 <= 2 * n ; L++) {
            int R = L + len - 1;
            int s = sum[R] - sum[L - 1];
            for (int k = L ; k < R ; k++) {
                dp[L][R][0] = min(dp[L][R][0], dp[L][k][0] + dp[k + 1][R][0] + s);
                dp[L][R][1] = max(dp[L][R][1], dp[L][k][1] + dp[k + 1][R][1] + s);
            }
        }
    }
    int mi = 1e9, mx = -1e9;
    for (int i = 1 ; i <= n ; i++) {
        mi = min(mi, dp[i][i + n - 1][0]);
        mx = max(mx, dp[i][i + n - 1][1]);
    }
    cout << mi << "\n" << mx;
    return 0;
}
习题

Problem - D - Codeforces

定义 \(dp_{i,j}\) 为第 \(i\) 个数到第 \(j\) 个数的最大得分，\(prod_i\) 表示前 \(i\) 个数乘积。

从小到大枚举长度进行区间dp即可。

代码
C++
 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
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 a[305], prod[305];
i64 dp[305][305];
const i64 P = 1000003;
i64 inv(i64 a, i64 b = P - 2, i64 res = 1) {
    while (b) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    prod[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        prod[i] = prod[i - 1] * a[i] % P;
    }
    for (int len = 2 ; len <= n ; len++) {
        for (int L = 1 ; L + len - 1 <= n ; L++) {
            int R = L + len - 1;
            for (int k = L ; k < R ; k++) {
                i64 s = prod[R] * inv(prod[k] % P) % P - prod[k] * inv(prod[L - 1]) % P;
                s = s * s;
                dp[L][R] = max(dp[L][R], dp[L][k] + dp[k + 1][R] + s);
            }
        }
    }
    cout << dp[1][n];
    return 0;
}