[区间dp] 石子合并(模板题+区间dp模型)_区间石子

0. 前言

区间 dp 问题第一维都是枚举区间长度，一般 len=1 用来初始化，枚举从 len=2 开始。第二维枚举起点 i，其中右端点 j 自动获得为 j = i + len - 1。

大多区间 dp 套路都是：

• 从小到大枚举区间长度
• 然后再从小到大枚举左端点，区间右端点直接通过计算得出。
• 最后在枚举分割点

三重循环，故数据范围一般都比较小，100 左右。

1. 区间dp 模板题

282. 石子合并

重点： 区间 dp、边界条件及初始化

思路：

• 状态定义：
  • f[i][j] 所有将第 i 到 j 堆石子合并成一堆石子所花费的代价的最小值。答案即为 f[1][n]
• 状态转移：
  • 分类依据：最后一步操作一定是将最后的两堆合并成一堆，则可以以最后合并时的分界线的位置进行状态分类
    • 例如，合并区间 [i:j] 石子，分界点为 k。即，进行最后一步合并操作，不妨设左区间为 [i:k]，右区间为 [k+1:j]
    • 合并 [i:j] 石子，就等价于合并 [i:k] 及 [k+1:j] 石子所各自花费的最小代价，再加上合并 [i:j] 这些总石子重量的固定代价，求 [i:j] 区间石子总重量可以预处理前缀和快速求得
    • 即状态转移方程为：f[i][j]=min(f[i][k], f[k+1][j]+s[j]-s[i-1])
• 边界处理及初始化
  • i==j 时，代表区间长度为 1，即 f[i][i] = 0，因为只有一堆石子是不需要进行合并的，花费代价为 0，故区间长度可以从 2 开始枚举。在此注意对全局数组直接 memset，导致 f[i][i] 变成极大值，会导致 f[1][n] 也成为极大值，因为 f[i][j] 内全是极大值，min 操作没有意义…在这卡了老半天…
  • 除 f[i][i] 外 f[i][j] 应该全部初始化为 INF，因为要进行 min 操作
  • 时间复杂度：
  • $O(n^3)$，枚举 i,j,k 各自占一个 $n$

区间 dp，这个循环的顺序是很重要的，即在计算 f[i][j] 的时候，f[i][j] 所依赖的所有状态应该都是计算好的。故这里的顺序就可以枚举区间长度，从区间长度为 1 开始顺序枚举。

注意全局初始化及区间长度为 1 时的初始化，代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main() {
    cin >> n;
    
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = 0;   // 一定不要忘记这个初始化...
    
    for (int i = 1; i <= n; ++i) cin >> s[i];
    
    for (int i = 1; i <= n; ++i) s[i] += s[i - 1];
    
    for (int len = 2; len <= n; ++len)		 // 区间 DP 枚举套路：长度+左端点 
        for (int i = 1; i + len - 1 <= n; ++i) {
            int l = i, r = i + len - 1;		 // 直接计算得到右端点
            for (int k = l; k < r; ++k)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    
    cout << f[1][n] << endl;
    
    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
33

一个不错的写法，代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main() {
    cin >> n;
    
    for (int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i - 1];
    
    for (int len = 2; len <= n; ++len)              // 区间长度为1,1堆石子合并的代价为0
        for (int i = 1; i + len - 1 <= n; ++i) {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;                          // 只对用到的进行初始化f[l][r] 且保证f[k+1][r]一定是计算过的
            for (int k = l; k < r; ++k)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    
    cout << f[1][n] << endl;
    
    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