【区间dp】 P1775 石子合并（弱化版） 题解

题目描述

设有 $N(N\le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots ,N$。每堆石子有一定的质量 $m_i(m_i\le 1000)$。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

思路

记 $d{p}_{l,r}$ 表示合并 $l$ 到 $r$ 的最小代价，则有以下转移方程：

$$d{p}_{l,r}=(\underset{k=l}{\overset{r}{\min }}d{p}_{l,k}+d{p}_{k+1,r})+\sum _{i=l}^r{m}_k$$

通俗的讲，从 $l$ 合并到 $r$ 最小代价等价于从 $l$ 合并到 $k$ 的最小代价再加上从 $k+1$ 合并到 $r$ 最小代价再加上两者总量和（即区间的总和）。其中

$$\sum _{i=l}^r{m}_k$$

可以通过前缀和做到处理时 $O(1)$，而枚举 $l,r,k$ 共复杂度 $O(n^3)$，可以通过本题。

因为枚举 $d{p}_{l,r}$ 要调用到 $d{p}_{l,k}$，需要按区间长度枚举，即区间 dp。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dp[305][305];
int m[305];
signed main() {scanf("%lld",&n);for(int i = 1;i <= n;i++) scanf("%lld",&m[i]),m[i] += m[i - 1];for(int i = 2;i <= n;i++) {for(int l = 1;l + i - 1 <= n;l++) {int r = l + i - 1;dp[l][r] = 1e18;for(int k = l;k <= r;k++) dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r]);dp[l][r] += m[r] - m[l - 1];}}printf("%lld\n",dp[1][n]);return 0;
}