有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

第一行一个整数n（n<=100）
第二行n个整数w1,w2…wn  (wi <= 100)

一个整数表示最小合并代价

4
4 1 1 4

18

题解：

这道题是一道很裸的区间DP
我们定义dp[i][j]为区间i到j得最小花费
dp[i][j] = min{dp[i][k] + dp[k+1][j] + sum(i, j)}
其中sum表示前缀和
这样转移为

for (int i = n; i >= 1; i--)
    for (int j = i + 1; j <= n; j++)
        dp[i][j] = 2147483647;
        for (int k = i; k <= j; k++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i+1]);

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long sum[233333], num[233333], dp[105][105];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
		sum[i] = sum[i-1] + num[i];
	}
	for (int i = n; i >= 1; i--)
	{
		for (int j = i + 1; j <= n; j++)
		{
			dp[i][j] = 2147483640;
			for (int k = i; k <= j; k++)
			{
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
			}
		}
	}
	cout << dp[1][n];
	return 0;
}
/*
100
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94 3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1 93 48 29 23 84 54 56 40 66 76 31 8 44 39 26 23 37 38 18 82 29 41
*/