题目链接：http://acm.swust.edu.cn/problem/code/745255/
Time limit(ms): 1000 Memory limit(kb): 65535
Description
以下方法称为最小代价的字母树：给定一正整数序列，例如：4，1，2，3，在不改变数的位置的条件下把它们相加，并且用括号来标记每一次加法所得到的和。
例如：（（4+1）+ （2+3））=（（5）+（5））=10。除去原数不4，1，2，3之外，其余都为中间结果，如5，5，10，将中间结果相加，得到：5+5+10= 20，那么数20称为此数列的一个代价，若得到另一种算法：（4+（（1+2）+3））=（4+（（3）+3））=（4+（6））=10，数列的另一个代价为：3+6+10=19。若给出N个数，可加N-1对括号，求出此数列的最小代价。
注：结果范围不超出longint.
例如：（（4+1）+ （2+3））=（（5）+（5））=10。除去原数不4，1，2，3之外，其余都为中间结果，如5，5，10，将中间结果相加，得到：5+5+10= 20，那么数20称为此数列的一个代价，若得到另一种算法：（4+（（1+2）+3））=（4+（（3）+3））=（4+（6））=10，数列的另一个代价为：3+6+10=19。若给出N个数，可加N-1对括号，求出此数列的最小代价。
注：结果范围不超出longint.
Input
第一行为数N(1≤N≤200)，第二行为N个正整数，整数之间用空格隔开。
Output
输出仅一行，即为最少代价值。
Sample Input
|
4
4 1 2 3
|
Sample Output
| 19 |
Hint
解题思路：一个dp问题dp[i][j] 表示区间[i,j]的最小代价，于是在dp[i][j]从中间找一个k值分成两部分尝试不同的数字组合，找出[i,j]内最小代价
于是得到了一个dp方程如下dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
#define min(a,b) a<b?a:b
#define inf 0x3f3f3f3f int sum[], dp[][]; //dp[i][j]表示区间[i,j]的最小代价
int main()
{
int n, i, j, k, r, x;
cin >> n;
memset(dp, inf, sizeof(dp));
for (i = ; i <= n; i++){
cin >> x;
sum[i] = sum[i - ] + x;
dp[i][i] = ;
}
for (r = ; r < n; r++){
for (i = ; i <= n - r; i++){
j = i + r;
for (k = i; k < j; k++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + ][j] + sum[j] - sum[i - ]);
}
}
}
cout << dp[][n] << endl;;
return ;
}
用类似的dp方法可以解决[Swust OJ 574]RentBoat [Swust oj 419]括号配对 [nyoj 37]回文字符串