【题目描述】

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

设计一个程序，计算出将N堆石子合并成一堆的最小得分。

【输入描述】

第一行为一个正整数N (2≤N≤100)；

以下N行,每行一个正整数，小于10000，分别表示第i堆石子的个数（1≤i≤N）。

【输出描述】

【样例输入】

7  13  7  8  16  21  4  18

【样例输出】

239

【题目分析】

1.定义状态：

设 dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小得分。

为了方便计算区间和，预处理一个前缀和数组 sum，其中 sum[i] 表示前 i 堆石子的总数。

2.状态转移方程：

对于区间 [i, j]，枚举最后一次合并的分割点 k（i ≤ k < j），将区间分成 [i, k] 和 [k+1, j]。

合并这两部分的得分为 sum[j] - sum[i-1]（即区间 [i, j] 的石子总数）。

状态转移方程为：

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);

3.初始化：

单个石堆不需要合并，因此 dp[i][i] = 0。

其他 dp[i][j] 初始化为一个较大值（如 INT_MAX）。

4.计算顺序：

按区间长度从小到大计算，因为长区间的结果依赖于短区间。

【参考答案】

#include <iostream>  #include <climits>  using namespace std;    const int MAX_N = 100;  // 最大石子堆数    int main() {  	int N;  	cin >> N;  	int stones[MAX_N + 1] = {0};  // 石子堆，从1开始编号  	int sum[MAX_N + 1] = {0};     // 前缀和数组  	for (int i = 1; i <= N; i++) {  		cin >> stones[i];  		sum[i] = sum[i - 1] + stones[i];  	}    	// DP表，dp[i][j]表示合并i到j堆的最小得分  	int dp[MAX_N + 1][MAX_N + 1] = {0};    	// 初始化：单个石堆不需要合并，得分为0  	for (int i = 1; i <= N; i++) {  		dp[i][i] = 0;  	}    	// 按区间长度从小到大计算  	for (int len = 2; len <= N; len++) {      // 区间长度  		for (int i = 1; i + len - 1 <= N; i++) {  // 区间起点  			int j = i + len - 1;              // 区间终点  			dp[i][j] = INT_MAX;  			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] << endl;  	return 0;  }