3. 石子项链
题目ID：8587必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
40 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
有N堆石子围成一圈，其中第i堆的石子的重量为Ai，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及获得的价值都是两堆石子的重量之和。求把全部N堆石子合并成一堆最多可以获得多少价值。
输入格式
第一行一个正整数N（N<=300），表示石子的堆数N。
第二行N个正整数，表示每堆石子的质量(<=1000)。
输出格式
一个正整数，表示最多获得多少价值。
样例
Input 1
4 2 6 7 2
Output 1
45
样例解释
将第1和第4堆石子合并，得到石子重量为2+2=4的新堆，合并后的价值为4；将第2和第3堆石子合并，得到石子重量为6+7=13的新堆，合并后的价值为13；将第4和第1堆石子合并，得到石子重量为4+6=10的新堆，合并后的价值为10。最终将第3堆和第1堆石子合并，得到石子重量为13+10=23的新堆，合并后的价值为23。因此，最多可以获得45的价值。
数据范围
N<=300，石子的质量<=1000
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N];
int dp[700][700];
int sum[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
a[n + i] = a[i];
}
for (int i = 1; i <= 2 * n; ++i) sum[i] = sum[i - 1] + a[i];
for (int len = 2; len <= 2 * n; ++len)
{
for (int l = 1; l + len - 1 <= 2 * n; ++l)
{
int r = l + len - 1;
for (int k = l; k < r; ++k)
{
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) ans + max(ans, dp[i][i + n - 1]);
cout << ans;
}