区间dp之 "石子合并"系列(未完结)

A. 石子合并<1>

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统评测 方式:文本比较
 
题目描述

有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆,规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为改次合并的得分,编一程序,由文件读入堆数n及每堆石子数(<=200);

(1)选择一种合并石子的方案,使得做n-1次合并,得分的总和最少

(2)选择一种合并石子的方案,使得做n-1次合并,得分的总和最多

输入格式

第一行为石子堆数n 第二行为每堆石子数,每两个数之间用一空格分隔。

输出格式

从第1行为得分最小第二行是得分最大。

样例输入

4
4 5 9 4
样例输出
44
54

分析:

附上代码(有注释):

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxp=210;
 6 int n,t[maxp],//t[i]:第i堆石子的个数 
 7 f_min[maxp][maxp],//f_min[i][j]:从i到j的最小得分 
 8 f_max[maxp][maxp],//f_max[i][j]:从i到j的最大得分 
 9 sum[maxp];//sum[i]:从1到i的石子总和 
10 int main(){
11     memset(f_min,0x3f,sizeof(f_min));//以上是进行初始值 min要给一个大的值,否则结果0 
12     scanf("%d",&n);
13     for(int i=1;i<=n;++i)
14         scanf("%d",&t[i]);//以上是输入 
15     for(int i=1;i<=n;++i)
16         sum[i]=sum[i-1]+t[i];
17     for(int i=1;i<=n;i++)
18         f_min[i][i]=0; //从i到i的最小合并恰好是0 
19     for(int len=1;len<n;len++){
20         for(int i=1;i+len<=n;i++){
21             int j=i+len;
22             for(int k=i;k<j;k++){
23                 f_min[i][j]=min(f_min[i][j],f_min[i][k]+f_min[k+1][j]);
24                 f_max[i][j]=max(f_max[i][j],f_max[i][k]+f_max[k+1][j]);
25             }
26             f_min[i][j]+=sum[j]-sum[i-1];//后面的添加语句是:从i到j的总和
27             f_max[i][j]+=sum[j]-sum[i-1];
28         }
29     }
30     printf("%d
%d",f_min[1][n],f_max[1][n]);
31     return 0;
32 }
View Code
原文地址:https://www.cnblogs.com/cdsidi/p/11273979.html