動態規劃入門合并石子 COGS1660 石子合并

1660. 石子合并（加強版）

★★?? 輸入文件：stone3.in?? 輸出文件：stone3.out???簡單對比
時間限制：1 s?? 內存限制：256 MB

【題目描述】

? 在一個圓形操場的四周擺放N堆石子,現要將石子有次序地合并成一堆.規定每次只能選相鄰的2堆合并成新的一堆，并將新的一堆的石子數，記為該次合并的得分。

? ? 試設計出1個算法,計算出將N堆石子合并成1堆最大得分.

【輸入格式】

數據的第1行試正整數N,1≤N≤2000,表示有N堆石子.第2行有N個數,分別表示每堆石子的個數.

【輸出格式】

輸出共1行,最大得分

【樣例輸入】

4 4 5 9

【樣例輸出】

【提示】

注意數據范圍。

【來源】

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 }

轉載于:https://www.cnblogs.com/sdfzxh/p/6808572.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/455765.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/455765.shtml
英文地址，請注明出處：http://en.pswp.cn/news/455765.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！