题目传送门
Problem Description
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
Input
有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
Output
输出总代价的最小值，占单独的一行
Sample Input
3
1 2 3
7
13 7 8 16 21 4 18
Sample Output
9
239
题解：
- 区间DP模板题
- 用dp[i][j]来表示合并第i堆到第j堆石子的最小代价。那么状态转移方程为 ：
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+cost[i][j]);
cost维护前缀和，有cost(i, j) = cost[j] - cost[i-1];
AC-Code：
#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <fstream>
#include <set>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;const int INF = 0x3f3f3f;
const int MAXN = 1e2 + 10;int max(int a, int b, int c) {
int t = a > b ? a : b;return t > c ? t : c;
}int dp[MAXN][MAXN];// 合并第i->j堆最小代价
int a[MAXN];
int cost[MAXN];//前缀和cost(a, b) = cost[b] - cost[a-1]
int main() {
int n;while (cin >> n) {
memset(dp, INF, sizeof dp);cost[0] = 0;for (int i = 1; i <= n; i++) {
cin >> a[i];cost[i] = cost[i - 1] + a[i];dp[i][i] = 0;}for (int len = 2; len <= n; len++) //区间长度for (int i = 1; i <= n; i++) {
//枚举起点int j = i + len - 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] + cost[j] - cost[i - 1]);}cout << dp[1][n] << endl;}return 0;
}