nyoj737 石子合并（一） 区间DP

    dp[x][y]表示合并[x, y]区间的石子的最小花费，将区间长度递增枚举即可。

  AC代码：

#include<cstdio>#include<algorithm>using namespace std;const int inf = 1 << 30;const int maxn = 200 + 5;int dp[maxn][maxn], a[maxn], sum[maxn];int solve(int n){	for(int i = 1; i < n; ++i) dp[i][i] = 0;	for(int i = 2; i <= n; ++i)		for(int j = 1; j <= n - i + 1; ++j){			int x = j, y = j + i - 1;			dp[x][y] = inf;			for(int k = j; k < y; ++k){				dp[x][y] = min((dp[x][k] + dp[k + 1][y]) + sum[y] - sum[x - 1], dp[x][y]);			} 		}	return dp[1][n];}int main(){	int n;	while(scanf("%d", &n) == 1){		sum[0] = 0;		for(int i = 1; i <= n; ++i) {			scanf("%d", &a[i]);			sum[i] = sum[i - 1] + a[i];		}		PRintf("%d/n", solve(n));	}	return 0;}如有不当之处欢迎指出！