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 4 5 9
【样例输出】
54
【提示】
注意数据范围。
【来源】
HZOI
注意范围......
题解观摩chy/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(){10scanf("%d",&n);11for(int i=1;i<=n;i++) scanf("%d",&in),sum[i]=sum[i-1]+in;12for(int i=1;i<=n;i++) sum[i+n]=sum[i]+sum[n]; 13ans=0x80000000;14for(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 }20for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);21printf("%d",ans);22return 0;23 }
