传送门 $\looparrowright$

题目描述

设有N堆沙子排成一排，其编号为 $1,2,3,\dots,N(N\leq 300)$ 。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这 $N$ 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 $4$ 堆沙子分别为 $1, 3 ,5, 2$ ，我们可以先合并 $1,2$ 堆，代价为 $4$ ，得到 $4, 5, 2$ ，又合并 $1,2$ 堆，代价为 $9$ ，得到 $9, 2$ ，再合并得到 $1$ ，总代价为 $4+9+11=24$ ，如果第二步是先合并 $2,3$ 堆，则代价为 $7$ ，得到 $4,7$ ，最后一次合并代价为 $11$ ，总代价为 $4+7+11=22$ 。问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

输入描述

第一行一个数 $N$ 表示沙子的堆数 $N$ 。
第二行 $N$ 个数，表示每堆沙子的质量 $(\leq1000)$ 。

输出描述

合并的最小代价

示例1

输入
4
1 3 5 2
输出
22

分析

经典区间 $\text{DP}$ 问题。
定义 $dp[i][j]$ 为合并区间 $[i,j]$ 的最小代价。则有 $dp[i][j]=\min\limits_{i\le k< j} \left(dp[i][k]+dp[k+1][j]+count(i,j)\right)$ （ $count(i,j)$ 为区间 $[i,j]$ 内石子的个数）。相当于将 $[i,j]$ 拆成两个区间 $[i,k]$ 和 $[k+1,j]$ ，两个区间各自合并石子需要 $dp[i][k]$ 和 $dp[k+1][j]$ 的代价，将两个区间合并要花费 $count(i,j)$ 的代价。
进行递推时，最外层循环为 $j$ ，控制右边界；第二层循环从 $j$ 到 $1$ ，控制左边界；第三层循环控制分界点。

代码

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#define N 302
using namespace std;
int dp[N][N];
int n;
int sum[N];
int a[N];
int main()
{
	memset(dp,0x3f,sizeof(dp));//初始化
	int i,j,k;
	cin>>n;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	//预处理前缀和,O(1)得到count(i,j)
	for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	//注意循环的顺序
	for(j=1;j<=n;j++)
	{
		//逆序更新，优先更新靠近边界的值
		for(i=j;i>=1;i--)
		{
			if(i==j) dp[i][j]=0;
			for(k=i;k<j;k++)
			{
				dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}