当前位置:首页 > 题解目录 > 正文内容

【题解】石子合并

亿万年的星光2个月前 (05-30)题解目录216

【题目描述】

在一个操场上一排地摆放着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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】夹角

【题目描述】这次童鞋们面临的问题是这样的:在一个平面内有两个点,求两个点分别和原点的连线的夹角的大小。注:夹角的范围[0,180],两个点不会在圆心出现。【输入描述】输入数据的第一行是一个数据T,表示...

【题解】最大子矩阵

【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。比如,如下4 × 4的矩阵0  -2 -7&nb...

2的幂次方表示

【题目描述】任何一个正整数都可以用2的幂次方表示。例如:137=27+23+20同时约定方次用括号来表示,即ab可表示为a(b)。由此可知,137可表示为:2(7)+2(3)+2(0)进一步:7=22...

【题解】发工资

【题目描述】作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵但是对于公司财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小李最近就在考虑一个问题:如果每...

【动态规划】完全背包

【题目描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为m,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于m,而价值的和...

【题解】寻找祖先

【题解】寻找祖先

【题目描述】给出充足的父子关系,请你编写程序找到某个人的最早的祖先。规定每个人的名字都没有空格,且没有任意两个人的名字相同。最多可能有1000组父子关系,总人数最多可能达到50000人,家谱中的记载不...