[普及/提高-]A54979.题解

题意（形式化）

有 $n$ 个数排成一排，第 $i$ 个是 $a_i$ ，每次选择两个相邻的数合并，例如选择了 $a_i$ 和 $a_{i+1}$，那么将会用一个数 $a_i + a_{i + 1}$ 代替原来的 $a_i$ 和 $a_{i+1}$，这个操作花费为 $a_1+a_{i+1}$。问经过数次操作后只剩下一个数时，这个花费的最小值是多少。

思路

对于最小花费或者最大花费的问题一般使用 dp 解决，这里考虑区间 dp。

设 $dp_{i,j}$ 为从第 $i$ 个史莱姆到第 $j$ 个史莱姆这个区间合并成一个史莱姆的最小花费。

显然易见，每个区间合并后其史莱姆大小是固定的，一定为该区间总和，故在合并两个史莱姆使其合并成一个区建从 $i$ 到 $j$ 的史莱姆时，一定为 $\sum_{k=i}^{j} a_k$。既然每次合并的花费都是固定的，那么转移方程就很明显了，枚举一个区间的分割线，算出被分割后两个区间的总花费最小值后加上 $\sum_{k=i}^{j} a_k$ 即可。

$$dp_{i , j} = \min_{i \le k < j} \left( dp_{i , k} + dp_{k + 1 , j} + \sum_{t=i}^{j} a_t \right)$$

而初始状态则是范围为一个史莱姆，一次都不用合并的情况，花费为 $0$。

$$dp_{i,i} = 0,\quad 1 \le i \le n$$

当然求和部分可以用时前缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 405;
int dp[N][N] , sum[N];
int slove(int l , int r){
	return sum[r] - sum[l - 1];
}
int n , a[N];
signed main(){
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
		for(int j = 1;j <= n;j ++){
			dp[i][j] = 0x3f3f3f3f3f3f3f3f;
		}
		dp[i][i] = 0;
	}
	for(int len = 2;len <= n;len ++){
		for(int i = 1;i <= n;i ++){
			int j = len + i - 1;
			if(j > n) break;
			for(int k = i;k < j;k ++){
				dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k + 1][j] + slove(i , j));
			}
		}
	}
	cout << dp[1][n];
	return 0;
}

实际上本体就是 P1775 石子合并（弱化版） 把范围改大了点而已，算是二倍经验。