Problem Description

一條直線上擺放著一行共n堆的石子。現(xiàn)要將石子有序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。

請編輯計算出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分。

Input?

輸入有多組測試數(shù)據(jù)。

每組第一行為n(n<=100)，表示有n堆石子，。

二行為n個用空格隔開的整數(shù)，依次表示這n堆石子的石子數(shù)量ai（0<ai<=100）

Output

每組測試數(shù)據(jù)輸出有一行。輸出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分。 中間用空格分開。

Sample Input

3

1 2 3

Sample Output

9 11

思路：石子合并問題之直線下的相鄰合并，具體思路：點擊這里

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 10007 #define E 1e-6 #define LL long long using namespace std; int a[N]; int sum[N]; int dp[N][N]; int main() {int n;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}memset(dp,INF,sizeof(dp));for(int i=1;i<=n;i++)dp[i][i]=0;for(int len=1;len<n;len++){for(int i=1;i<=n-len;i++){int j=i+len;for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);dp[i][j]+=sum[j]-sum[i-1];}}printf("%d ",dp[1][n]);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)dp[i][i]=0;for(int len=1;len<n;len++){for(int i=1;i<=n-len;i++){int j=i+len;for(int k=i;k<j;k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);dp[i][j]+=sum[j]-sum[i-1];}}printf("%d\n",dp[1][n]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的石子合并问题--直线版（Hrbust-1818）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。