6. 石子合并2
题目ID：15699拓展题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
有N堆石子排成一圈,其中第i堆的石子的重量为Ai，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及消耗的体力都是两堆石子的重量之和。求把全部N堆石子合并成一堆最少需要消耗多少体力。
输入格式
第一行一个正整数N（N<=300），表示石子的堆数N。第二行N个正整数，表示每堆石子的质量(<=1000)。
输出格式
一个正整数，表示最少需要消耗多少体力。
样例
Input 1
4 1 3 5 2
Output 1
20
我的代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 310;
int n,dp[1010][1010],a[1010],sum[10010];
int main() {
cin >> n;
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
dp[i][j] = INT_MAX;
}
}
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
a[i + n] = a[i];
}
for(int i = 1 ; i <= 2 * n ; i++) {
dp[i][i] = 0;
sum[i] = sum[i - 1] + a[i];
dp[i][i + 1] = a[i] + a[i + 1];
}
for(int len = 2 ; len <= 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] = min(dp[l][r],dp[l][k] + dp[k + 1][r]+sum[r] - sum[l-1]);
}
}
}
int ans = 1e9;
for(int i = 1 ; i <= n ; i++) {
ans = min(ans,dp[i][i + n - 1]);
}
cout << ans << endl;
return 0;
}
动规大方向对了，班里好几个人看了很久愣是没看出来