1048 石子归并 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
题解 查看运行结果
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n（n<=100）
第二行n个整数w1,w2…wn (wi <= 100)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
思路：
动规 转移方程:f[i][j] = max(f[i][j] , f[i][k]+f[k+1][j]+sum[i][j])
代码
#include<iostream>#include<string.h>#include<math.h>#include<algorithm>#include<stdio.h> using namespace std;int f[101][101];int sum[101][101];int INF = 0x7fffffff;//这里代表int最大值，即最大移动石子的最少质量必须少于这个，不然超int int main(){ int n; scanf("%d",&n); int stone[101]; for(int i = 1;i<=n;i++){ scanf("%d",&stone[i]); } //求出任意间石头总数，表示当前归并需要累加的值。如[1][3]表示，在归并1-3堆石子时，从第二步到第三步需要移动的石头数 for(int i = 1;i<=n;i++){ for(int j=i;j<=n;j++){ sum[i][j] = sum[i][j-1]+stone[j];//初始化 } } for(int len = 2;len<=n;len++){ for(int i = 1;i<=n-len+1;i++){ int k = i+len-1; f[i][k] = INF; //设置i-k最大，然后取最小 for(int j = i;j<=k-1;j++){//前一步的结果要加上本步的结果，选出最佳 .所以这里要再退前一步 if(f[i][k]>f[i][j]+f[j+1][k]+sum[i][k]){ f[i][k] = f[i][j]+f[j+1][k]+sum[i][k]; } } } } PRintf("%d",f[1][n]); return 0;}新闻热点
疑难解答
