石子合并问题（动态规划）

有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成一堆，并将新的一堆的石子数，记为该次合并的得分，编一程序，给出堆数n及每堆石子数(<=200)；

（1）选择一种合并石子的方案，使得做n-1次合并，得分的总和最少

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

输入格式:
第一行为石子堆数n

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

输出格式:
第一行为最小合并得分，第二行是最大的合并得分。

输入样例:
在这里给出一组输入。例如：

4
4 5 9 4
输出样例:
在这里给出相应的输出。例如：

44
54

分析：



实现代码如下

#include<iostream>
#include<algorithm>
using namespace std;
int dpmin[1024][1024]={0},dpmax[1024][1024]={0};
int main(){
    int n,a[1024],sum[1024]={0};
    sum[0]=0;
    cin>>n;
    for(int i=1;i<=n;i++){
         cin>>a[i];
         sum[i]=sum[i-1]+a[i];
    }
    for(int length=2;length<=n;++length){
        for(int begin=1;begin<=n-length+1;++begin){
            int end=begin+length-1;
            dpmin[begin][end]=200000;//这里很关键，由题目可得最多为200000个石子
            dpmax[begin][end]=-1;//这里也很关键，需设置一个负数
            int temp=sum[end]-sum[begin-1];
            for(int k=begin;k<end;++k){
                dpmin[begin][end]=min (dpmin[begin][end],dpmin[begin][k]+dpmin[k+1][end]+temp);
                dpmax[begin][end]=max (dpmax[begin][end],dpmax[begin][k]+dpmax[k+1][end]+temp);
            }
        }
    }
    cout<<dpmin[1][n]<<endl;
    cout<<dpmax[1][n]<<endl;
    return 0;
}