1660. 石子合并（加強(qiáng)版）

★★?? 輸入文件：stone3.in?? 輸出文件：stone3.out???簡單對(duì)比
時(shí)間限制：1 s?? 內(nèi)存限制：256 MB

【題目描述】

?

? 在一個(gè)圓形操場(chǎng)的四周擺放N堆石子,現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相鄰的2堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。

?

? ? 試設(shè)計(jì)出1個(gè)算法,計(jì)算出將N堆石子合并成1堆最大得分.

?

【輸入格式】

數(shù)據(jù)的第1行試正整數(shù)N,1≤N≤2000,表示有N堆石子.第2行有N個(gè)數(shù),分別表示每堆石子的個(gè)數(shù).

【輸出格式】

輸出共1行,最大得分

【樣例輸入】

4

4 4 5 9

【樣例輸出】

54

【提示】

注意數(shù)據(jù)范圍。

【來源】

HZOI2014

?

注意范圍......

題解觀摩chy?http://blog.csdn.net/sdfzchy/article/details/70990830

?

貼代碼

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 int in,f[4010][4010],sum[4010]; 8 int ans,n; 9 int main(){ 10 scanf("%d",&n); 11 for(int i=1;i<=n;i++) scanf("%d",&in),sum[i]=sum[i-1]+in; 12 for(int i=1;i<=n;i++) sum[i+n]=sum[i]+sum[n]; 13 ans=0x80000000; 14 for(int i=2;i<=n;i++) 15 for(int s=1;s<=2*n-i+1;s++){ 16 int e=i+s-1; 17 f[s][e]=max(f[s+1][e],f[s][e-1]); 18 f[s][e]+=sum[e]-sum[s-1]; 19 } 20 for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]); 21 printf("%d",ans); 22 return 0; 23 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sdfzxh/p/6808572.html

總結(jié)

以上是生活随笔為你收集整理的动态规划入门 合并石子 COGS1660 石子合并的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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