题解：P1775 石子合并（弱化版）
yu10001909
·
·
题解
这是几乎所有 区间dp 学习者都要做的模板题，因此我想借这个题目梳理一下动态规划的思路。
原题传送门
题意简述
# 渐进式思路
## 递归函数
我们用函数 $\operatorname{solve}(l,r)$ 表示合并初始第 $l$ 堆到第 $r$ 堆石子所需的最小代价总和。
很明显：最后合并成的那堆石子一定是由两堆合并起来的。
而题目中合并的都是 **相邻** 的石子堆，也 **没有分离石子的操作**，所以最后一次合并的两堆石子的分界线就是原来那些石子的分界线之一。
所以我们可以 **枚举所有分界线**（更简单的说，我们枚举分界线左边的石子堆编号），那么最后的石子堆的最小代价就是左右两堆石子的最小代价加上合并所需代价。
更深入的，我们发现，合并所需代价是被合并的石子的质量和，他是一个定值，即调查范围内石子质量的总和。
因此，对于一个确定的分界线（这里设为 $i$），递归函数为：
$$
\operatorname{solve}(l,r)=\operatorname{solve}(l,i)+\operatorname{solve}(i+1,r)+\sum_{j=l}^{r}m_j
$$
如果我们把质量和记为 $sum$，函数即为：
$$
\operatorname{solve}(l,r)=\operatorname{solve}(l,i)+\operatorname{solve}(i+1,r)+sum
$$
函数下界则是：
$$
\operatorname{solve}(k,k)=0
$$
最后输出 $\operatorname{solve}(1,n)$ 就好了。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
int n, m[N];
int solve(int l, int r) {
if (l == r) return 0;
int sum = 0;
for (int i = l; i <= r; i++) sum += m[i];
int ans = 1 << 30;
for (int i = l; i < r; i++) ans = min(ans, solve(l, i) + solve(i + 1, r) + sum);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &m[i]);
printf("%d\n", solve(1, n));
return 0;
}
```
然而……[40pts](https://www.luogu.com.cn/record/231707272)
时间太慢了。
## 记忆化搜索
我们可以看到，其实很多函数是被调用了很多次的，例如：$n=4$ 时，$\operatorname{solve}(2,2)$ 就足足被调用了 $6$ 次！这大大降低了程序的运行效率。
由此，我们有了优化的方法：把每次的答案记录下来（$f_{i,j}$），这样只需要递归一次就好了。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
int n, m[N], f[N][N];
int solve(int l, int r) {
if (l == r) return 0;
int sum = 0;
if ( f[l][r] < 1 << 30 ) return f[l][r]; // 实质是 f[l][r] 被统计过了，不理解的可以代入极端值试一试。
for (int i = l; i <= r; i++) sum += m[i];
int &ans = f[l][r]; // 指针函数，避免每次代码都写太长，增加代码可读性。
for (int i = l; i < r; i++) ans = min(ans, solve(l, i) + solve(i + 1, r) + sum);
return ans;
}
int main() {
scanf("%d", &n);
memset(f, 127, sizeof(f)); // 初始化，每个数的值是 1111111011111110111111101111111(二进制)，比 1 << 30 大一点。
for (int i = 1; i <= n; i++)
scanf("%d", &m[i]);
printf("%d\n", solve(1, n));
return 0;
}
```
这样就是 [100pts](https://www.luogu.com.cn/record/231713282) 了
但是还不够。
## 动态规划
终于进入正题了。
动态规划实质上就是把记忆化搜索的过程正过来，用一段程序而非函数表示（个人认为目的是避免栈溢出，望指正）。
很明显，大范围的石子合并需要小范围的石子合并做基础，因此我们的方法是：
1. 从小到大枚举合并范围（堆数）$len$；
2. 从小到大枚举左端点 $i$；
3. 算出右端点 $j$，同时算出 $sum$（见上文）；
4. 从小到大枚举分界线 $k$；
5. 计算 $dp_{i,j}$（惯例，动规数组一般用 $dp$ 表示）。
这就是最简单的区间动态规划了。
下面我们来考察动态规划的四个特性：
### 最优子结构
明显，每个小范围的最小代价可以带来大范围的最小代价，因此该问题具有最优子结构。
### 无后效性
这里我们只关心最小代价是多少，并不担心是如何合并的，因此问题具有无后效性。
### 递推方程
$$
\operatorname{solve}(i,j)=\operatorname{solve}(i,k)+\operatorname{solve}(k+1,j)+sum
$$
### 边界
对于任意的 $i$，$\operatorname{solve}(i,i)=0$。因此这个递推是有界的不会无限递归。
于是我们断定，我们写的动规是有效的。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
int n, m[N], dp[N][N];
int main() {
scanf("%d", &n);
memset(dp, 127, sizeof(dp));
for (int i = 1; i <= n; i++) {
scanf("%d", &m[i]);
dp[i][i] = 0;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
int sum = 0;
for (int k = i; k <= j; k++) {
sum += m[k];
}
for (int fen = i; fen < j; fen++) {
dp[i][j] = min(dp[i][j], dp[i][fen] + dp[fen + 1][j] + sum);
}
}
}
printf("%d\n", dp[1][n]);
return 0;
}
```
依然 [100pts](https://www.luogu.com.cn/record/231704440)
## 还有优化吗？
我可以很负责任的告诉你：有的，兄弟，有的。
学了前缀和的都知道，求区间和这个事情是可以预处理的：
$$
s_{i+1} = s_i + m_{i+1}\\
sum_{i,j}=s_j-s_{i-1}
$$
简单来说：
$$
s_i = m_1+m_2+\cdots+m_i
$$
所以（前缀和特供）：
$$
\begin{aligned}
sum_{i,j}&=m_i+m_{i+1}+\cdots+m_j\\
&=(m_1+m_2+\cdots+m_j)-(m_1+m_2+\cdots+m_{i-1})\\
&=s_j-s_{i-1}
\end{aligned}
$$
于是终极代码就出现了：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
int n, m[N], dp[N][N], s[N];
int main() {
scanf("%d", &n);
memset(dp, 127, sizeof(dp));
s[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &m[i]);
dp[i][i] = 0;
s[i] = s[i - 1] + m[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for (int fen = i; fen < j; fen++) {
dp[i][j] = min(dp[i][j], dp[i][fen] + dp[fen + 1][j] + s[j] - s[i - 1]);
}
}
}
printf("%d\n", dp[1][n]);
return 0;
}
```
我们的学习旅程也就结束了。
# 更多
大家可以想一想为什么不用开 `long long`。
[更多经验点这里](https://www.luogu.com.cn/problem/P1880)，大家可以想一想环形的石子应该怎么做