题目
19182 石子合并（基础版）
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: 不限定
Description
设有 N(N≤300) 堆石子排成一排，其编号为1,2,3,⋯,N。每堆石子有一定的质量 mi(mi≤1000)。
现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。
合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。
输入格式
第一行，一个整数 N。
第二行，N 个整数 mi。
输出格式
输出仅一个整数，也就是最小代价。（题目确保答案在int范围）
输入样例
4
2 5 3 1
输出样例
22
提示
区间动态规划。题解可参考 11078 不能移动的石子合并（优先做）
点击查看代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define N 301
using namespace std;
int s[N]; // (前缀和)s[i]表示前i个整数之和
int dp[N][N]; // dp[i][j]表示将第i个石头到第j个石头合并在一起的方案集合中的最小代价
int main()
{
memset(dp, 0x7f, sizeof(dp)); // 给dp每个位置设置最大值，因为后面要用min找最小代价
int n;
cin >> n;
s[0] = 0;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] += s[i - 1];
dp[i][i] = 0; // 自己和自己不用合并，代价是0
}
for(int len = 2; len <= n; len++) // 合并长度范围
{
for(int l = 1; l + len - 1 <= n; l++) // 合并集合的左边界
{
int r = l + len - 1; // 合并集合的右边界
for(int mid = l; mid < r; mid++) // 将集合拆分成两部分
{
dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r] + s[r] - s[l - 1]); // 找到最小代价
}
}
}
cout << dp[1][n];
return 0;
}
放自己博客复习用
转发自
https://blog.csdn.net/weixin_54218079/article/details/127969565