D - 石子合并问题

D - 石子合并问题

Description

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 对于给定n堆石子,计算合并成一堆的最小得分和最大得分。

Input

输入数据的第1行是正整数n，1≤n≤100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。

Output

输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。

Sample

Input 

4 4 4 5 9

Output 

43 54

AC代码：

#include <iostream> #include <algorithm> #include <memory.h> #define inf 0x3f3f3f3f using namespace std; int main() { int n,i,j,k,a[202],dp[202][202],dpm[202][202]; cin>>n; memset(dp,0,sizeof(dp)); memset(dpm,0,sizeof(dpm)); for(i=1;i<=n;i++) { cin>>a[i]; a[i+n]=a[i]; } int sum[202];sum[0]=0; for(i=1;i<=2*n;i++) { sum[i]=sum[i-1]+a[i]; } for(i=2*n-1;i>=1;i--) { for(j=i+1;j<i+n&&j<=2*n;j++) { dpm[i][j]=inf; for(k=i;k<j;k++) { dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);//这是重点 dpm[i][j]=min(dpm[i][j],dpm[i][k]+dpm[k+1][j]+sum[j]-sum[i-1]); } } } int maxx=-1,minn=inf; for(i=1;i<=n;i++)//n个区间的值进行比较 { maxx=max(maxx,dp[i][i+n-1]); minn=min(minn,dpm[i][i+n-1]); } cout<<minn<<endl; cout<<maxx<<endl; return 0; }