將n堆石子繞圓形操場排放，現要將石子有序地合并成一堆，規定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數記做該次合并的得分，
請撰寫一個程式，讀入堆數n及每堆的石子數，并進行如下計算：
1.選擇一種合并石子的方案，使得做n-1次合并得分總和最大，
2.選擇一種合并石子的方案，使得做n-1次合并得分總和最小，
輸入描述:
輸入第一行一個整數n，表示有n堆石子，
第二行n個整數，表示每堆石子的數量，
輸出描述:
第一行為合并得分總和最小值，
第二行為合并得分總和最大值，
示例1
輸入
4
4 5 9 4
輸出
43
54
#include<bits/stdc++.h>
using namespace std;
int a[405],sum[405],f[405][405],n;
int fun()
{
for(int l=2;l<=n;++l)
for(int i=1,j=l;j<2*n;++i,j=i+l-1)
{
f[i][j]=1<<30;
for(int k=i;k<j;++k)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
int ans=1<<30;
for(int i=1;i<=n;++i) ans=min(ans,f[i][i+n-1]);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",a+i), sum[i]=sum[i-1]+a[i];
for(int i=n+1;i<2*n;++i)
a[i]=a[i-n], sum[i]=sum[i-1]+a[i];
printf("%d\n",fun());
for(int i=1;i<=2*n;++i)sum[i]=-sum[i];
printf("%d",-fun());
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266290.html
標籤：其他
下一篇：（干貨）掃雷游戲的實作