【问题描述】
在一个操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
【输入文件】
输入第一行为n(n<1000)，表示有n堆石子，第二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量（<=1000）
【输出文件】
输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
【输入样例】
3 1 2 3
【输出样例】
9 11
【分析思路】
对于区间[i,j]，枚举以k(k=i~j-1)为分界线求[i,k]与[k+1,j]的最大价值和的最大值。 当i==j时，不需要合并故价值为val[i]；
【代码实现】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0xfffffff
#define REP(a,b) for(int i=a;i<=b;i++)
#define RES(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,w[
120],dp[
120][
120],pre[
120];
int solve(
int l,
int r){
if(dp[l][r]!=-
1)
return dp[l][r];
if(l==r)
return dp[l][r]=
0;
int sum=pre[r]-pre[l-
1],ans=
10000000;
REP(l,r-
1){
ans=min(ans,solve(l,i)+solve(i+
1,r));
}
return dp[l][r]=ans+sum;
}
int main(){
RES(dp,-
1); pre[
0]=
0;
scanf(
"%d",&n);
REP(
1,n) {
scanf(
"%d",&w[i]);
pre[i]=pre[i-
1]+w[i];
}
printf(
"%d",solve(
1,n));
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081416.html
相关资源：数据结构—成绩单生成器
