#include <bits/stdc++.h>
using namespace std;
int a[666];
int dp[610][610];
int sum[610];
int 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 <= n;i++){
sum[i] = sum[i-1] + a[i];
}
for (int len = 2;len <= n;len++){
for (int l = 1,r = len + l -1;r <= n;l++,r++){
for (int k = l;k < r;k++){
dp[l][r] = max(dp[l][r],dp[l][k] + dp[k+1][r]);
}
}
}
int maxn = INT_MIN;
for (int i = 1;i <= n;i++){
if(dp[i][i+n-1] >= maxn){
maxn = dp[i][i+n-1];
}
}
cout << maxn;
return 0;
}
1 个赞
题面
1 个赞
题目描述
有N堆石子围成一圈，其中第i堆的石子的重量为Ai，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及获得的价值都是两堆石子的重量之和。求把全部N堆石子合并成一堆最多可以获得多少价值。
输入格式
第一行一个正整数N（N<=300），表示石子的堆数N。
第二行N个正整数，表示每堆石子的质量(<=1000)。
输出格式
一个正整数，表示最多获得多少价值。
样例
Input 1
4 2 6 7 2
Output 1
45
数据范围
N<=300，石子的质量<=1000
样例解释
将第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的价值。
2 个赞
我也没AC，无语
2 个赞
我看看，这题区间DP
2 个赞
for (int len = 2;len <= n;len++){
for (int l = 1,r = len + l -1;r <= n;l++,r++){
for (int k = l;k < r;k++){
dp[l][r] = max(dp[l][r],dp[l][k] + dp[k+1][r]);
}
}
}
改成
for (int len = 2;len <= n;len++){
for (int l = 1,r = len + l -1;r <= n;l++,r++){
dp[l][r]=INT_MAX;
for (int k = l;k < r;k++){
dp[l][r] = min(dp[l][r],dp[l][k] + dp[k+1][r]);
}
}
}
3 个赞
然后直接输出dp[1][n]
2 个赞
不是，你状态转移方程
2 个赞
应该是dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]+sum[r]-sum[l-1]);
3 个赞
我的j就是你的k
2 个赞