(区间dp) (经典例题) 石子合并
文章目录
- 前言
- Code
- 常规写法
- 平行四边形优化
- 记忆化dfs
- 变种例题
- Dire Wolf
- END
前言
本文模板题：洛谷：P1775 石子合并（弱化版）
石子合并是区间dp的一道经典例题。各种变形也是层出不穷，最经典的就是"环形石子合并"，而解决思路就是破环成链
石子合并和最长回文子序列这类区间dp的最大不同在于有分割[i, j]区间的思想，因此时间复杂度是
O
(
n
3
)
{O(n^3)}
O(n3)，一般能过1e2量级的题目，而到了1e3量级的就需要四边形不等式优化来处理
本文不从0开始就讲解，重点讲解一些容易出错的细节地方
Code
常规写法
一下以区间范围
[1, n]来进行思考
- 状态定义
定义
dp[i][j]为区间i到j的某种状态，i>=j因此二维数组中的
i > j的部分是不需要的，在普通石子合并的时候一般不用在意
- 初始化
求最小值，一般来说初始就需要定义成最大值，这里我们初始为无穷大INF
长度为1时，即单个点不需要合并，因此值为0
注意：
i == j是长度为1的状态，特殊化处理i > j是合法的状态，定义为INFi < j是不合法的状态，要根据题意来定义
- 状态转移
在分割
[i, j]区间的时候找出点k将其分为两段
[i, k]和[k+1, j]在进行松弛操作注意：
k循环的范围
for (int k = i; k < j; k++)是[i, j)左闭右开因此最后的k=j-1 此时区间范围是
[i, j-1], [j, j]当
len >= 2是合法状态，这么写完全正确但是，若k循环时k<=j，或者len=1开始时又会如何呢？
k <= j会出现这种情况，[j+1, j]；这是不合法的状态
- 首先这么写必须把dp数组开到n+2的范围，防止越界
- 在定义时要把[i, j] (i > j) 也定义成INF，因为只有这么写，才能保证这个不合法的状态不会被松弛更新到
len == 1有时有的题可以直接在区间dp时从len=1开始
- 首先若在dp前已经对len=1操作了那可以当没事发生
- 若必须在dp中计算得，那必须让k<=j出现等号，这又回到了上一个特殊情况
- 关于区间范围 [1, n]
若定义为[0, n-1]可不可以？当然可以！
但是对于各种情况的处理会更加麻烦与让人疏忽
最显而易见的就是针对本题的前缀和会处理的稍微麻烦点
其次对于出现
[i, i-1], [j+1, j]这种因写法或者题型可能，或者必然需要处理到的情况，非常麻烦，而且容易出错我们算法选手通常会把数组开大，这样容易后面延伸
但是若定义了[0, n-1] 又遇到了 [i, i-1]就可能会出现[0, -1]这种非常可怕的数组越界情况
这种情况极难发现，而且不同语言，或者同一语言的不同数组，处理方式完全不一样
因此： 建议把区间范围定到
[1, n]dp数组开到dp[n+2][n+2]
本题只是把区间分成两个连续分段，其实还有很多其他情形不会这么简单的分割
本文最后会给出一道例题展示
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int n;
cin >> n;
vector<int> arr(n + 1); // 点权
vector<int> sum(n + 1); // 预处理前缀和
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
// 初始长度为1的时候
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
}
// 从长度为2开始考虑
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
// 枚举中间分割点 分成[i, k], [k+1, j]
// 注意这里的k<=j也行，但是注意下标越界问题
for (int k = i; k < j; k++) {
// 松弛每个分割点，加整体的价值(前缀和预处理)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
平行四边形优化
详细讲解的博客：
(详解)区间DP —— 平行四边形优化_一个很懒的人的博客-CSDN博客
四边形不等式优化 --算法竞赛专题解析（10）_罗勇军的博客-CSDN博客
关于四边形优化个人理解还不是很透彻，只能随便说说了，建议看下上面两篇博客
经过四边形优化复杂度可以接近 O ( n 2 ) {O(n^2)} O(n2)
前提：
- 区间包含的单调性
- 四边形不等式
重要结论：
已知在数轴有四个点
a <= b <= c <= d，同样定义i <= j
[a, c] + [b, d] <= [a, d] + [b, c]证明略[i, j] <= [i, j+1] <= [i+1, j+1]
- [i, j] ⊆ [i, j+1] && len([i, j]) <= len([i, j+1])
- [i, j+1] ⊆ [i+1, j+1] && len([i, j+1]) <= len([i+!, j+1])
将第二点的j整体减少一个单位，此时[i, j]正好落在中间
[i, j-1] <= [i, j+1] <= [i+1, j]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n + 1);
vector<int> sum(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
// 保险点开到 [0, n+1]
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0x3f3f3f3f));
// 平行四边形优化，s[][]表示[i,j]中的最优分割点
vector<vector<int>> s(n + 2, vector<int>(n + 2));
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
s[i][i] = i; // 当前点本身就是最优
}
for (int len = 2; len <= n; len++) {
for (int i = 1, j = i + len - 1; j <= n; i++, j++) {
for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) {
if (dp[i][j] > dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
s[i][j] = k; // 保持单调性，不断更新更大值
}
}
}
}
cout << dp[1][n] << endl;
return 0;
}
记忆化dfs
dp 自底向上
dfs 自顶向下 注意要用记忆化
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int M = 10 + 300;
int arr[M];
int sum[M];
int dp[M][M];
int dfs(int left, int right) {
// 考虑越界情况，视为不存在为0
if (left > right) {
return 0;
}
if (left == right) {
return 0;
}
// 记忆化dfs
if (dp[left][right] != INF) {
return dp[left][right];
}
for (int k = left; k < right; k++) {
dp[left][right] =
min(dp[left][right],
dfs(left, k) + dfs(k + 1, right) + sum[right] - sum[left - 1]);
}
return dp[left][right];
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
memset(dp, INF, sizeof(dp));
cout << dfs(1, n) << endl;
return 0;
}
变种例题
Dire Wolf
杭电：Dire Wolf - 5115
本题为：2014ACM/ICPC亚洲区北京站 (ACM真题)
题目大意：
有N匹狼🐺排成一排
每匹狼有自身战斗力arr[]和辅助战斗力brr[]，(辅助战斗力可以帮助相邻边上的一位)
每干掉一匹狼则该狼视为在队伍中消除
e.g. [a, b, c] 干掉b需要arr[b] + brr[a] + brr[c]
此时队伍变为[a, c]， 干掉a需要arr[a] + brr[c]
求：干掉所有狼的最小值
思路：
这里的分割不再是两段而是
[i, k-1], [k], [k+1, j]注意：这里的辅助值是
brr[i - 1] + brr[j + 1]是因为我们把[i, j]当作了一个整体，我们在尝试在整体内找分割点k的最优
k循环需要[i, j]闭区间
for (int k = i; k <= j; k++)考虑整体的每个点因为出现了
[i, k-1], [k+1, j]那必然会出现[i, j] i > j的不合法情况考虑到本题的第一匹狼没有左边，最后一匹狼没有右边
[i, k-1], [k+1, j]必然不合法而空位置可以理解为边上的辅助值为0，因此直接把不合法的位置赋初值为0
考虑完所有的这些情况，也可以让len从1开始dp
这里
len == 1则i == j
dp[i][k - 1] + dp[k + 1][j] + arr[k] + brr[i - 1] + brr[j + 1]等价于
dp[k][k-1] + dp[k+1][k] + arr[k] + arr[k-1] + arr[k+1]即
不合法0 + 不合法0 + 当前值 + 左边辅助 + 右边辅助同样符合状态转移
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 10 + 200;
const int INF = 0x3f3f3f3f3f3f3f3f;
int arr[M]; // 点权
int brr[M]; // 相邻的辅助值
int dp[M][M]; // 区间dp
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int j = 1; j <= n; j++) {
cin >> brr[j];
}
brr[0] = brr[n + 1] = 0; // 最外的两边视为0
// [j, i] 相对位置错误归零
// [i, j] 需要求的位置初始为INF
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i][j] = 0;
}
for (int j = i; j <= n; j++) {
dp[i][j] = INF;
}
}
// 注意k循环中的 k-1,k+1的数组范围
// 因此自己定义需要dp[n+2][n+2]
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
// [i, j]中每个点来划分
// 分为三段 [i, k-1] [k] [k+1, j]
for (int k = i; k <= j; k++) {
dp[i][j] = min(dp[i][j],
dp[i][k - 1] + dp[k + 1][j] + // 两边的dp
arr[k] + // 单个点的点权
brr[i - 1] + brr[j + 1]); // 该区间外的两边
}
}
}
cout << dp[1][n] << endl;
}
signed main() {
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++) {
printf("Case #%lld: ", i);
solve();
}
return 0;
}