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

【题解】石子合并

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

【题目描述】

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


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

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

分享给朋友:

相关文章

【循环】日记第几天

【题目描述】小明每天都坚持写日记,突然有一天小明在想,我今年写了多少篇日记了?一篇一篇的数好麻烦,没办法小明只能把这个艰难的问题交给聪明的你来解决。【输入描述】输入三个整数�y,m,d分别表示年月日,...

【题解】求最长不下降序列

【题目描述】设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j),若存在i1<i2<i3<…<ie 且有b...

【题解】AC

4.AC(ac.cpp) 【问题描述】 小明获得了一行字符串,他想知道在不改变字符顺序的情况下,从前到后最多能组合出多少个ac? (a和c的位置可以不连续)比如:字符串为addca...

数列

数列

【题目描述】有一个分数序列求出这个序列的前n项和,结果保留两位小数。(注意,不用通分,单项相加即可)【输入描述】一个数字,N【输出描述】前N项的和【样例输入】10【样例输出】16.48【题目分析】(1...

【题解】分糖果

【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

【题解】高精度除法

【题目描述】高精除以高精,求它们的商和余数。【输入描述】输入两个低于300位的正整数。【输出描述】输出商和余数。【样例输入】12313123184575776878979876423245678643...