【NOIP2006】【Luogu1063】能量项链
【摘要】
problem
给定 n 颗环形串起来的珍珠,每个珍珠有头标记 hi 和尾标记 ti,按照任意顺序合并相邻珍珠 u, v,会带来 hu ∗ tu ∗ tv 的收益,并且会结合成新的珍珠 w,其中 hw ...
problem
给定 n 颗环形串起来的珍珠,每个珍珠有头标记 hi 和尾标记 ti,按照任意顺序合并相邻珍珠 u, v,会带来 hu ∗ tu ∗ tv 的收益,并且会结合成新的珍珠 w,其中 hw = hu, tw = tv。保证相邻珍珠同侧标记相同。求最大收益。
数据范围 n ≤ 100
solution
环形DP,拆换成链,做区间DP。
记dp[i][j] 表示原珍珠串的 i..j 合并成一段的最大收益。转移枚举最后一次合并的分割点。
dp[i][j] = max{dp[i][k] + dp[k + 1][j]+hi∗tj∗tk} 而原序列是环形的,我们只需要倍长原序列即可。 时间复杂度 O(n^3)
codes
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 330;
int a[maxn], f[maxn][maxn];
int dp(int l, int r){
if(f[l][r])return f[l][r];
if(l==r-1)return a[l]*a[r]*a[r+1];//每颗珠子自己的能量
for(int k = l; k < r; k++)//k从i开始因为你自己一堆,右边的全部一堆也是一种情况。
f[l][r] = max(f[l][r],dp(l,k)+dp(k+1,r)+a[l]*a[k+1]*a[r+1]);
return f[l][r];
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){ cin>>a[i]; a[n+i]=a[i];}
int ans = 0;
for(int i = 1; i <= n; i++)ans = max(ans, dp(i,n+i-1));
cout<<ans;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
//环形DP, 复制一份, 拆环成链,然后做区间DP(即对每条链做一遍区间DP,取最大值。)
//解释一下, 注释详细度主要看心情。。。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int w[maxn], f[maxn][maxn];
int dp(int i, int j){
if(f[i][j])return f[i][j];
//注意边界, [i~i,i+1~j] and [i~j-1,j~j];
for(int k = i; k <= j-1; k++)
//通过k合并后, 两颗珠子分别为[i,k],[k+1,j]其中计算能量时headi*taili*headj;
f[i][j] = max(f[i][j], dp(i,k)+dp(k+1,j)+w[i]*w[k+1]*w[j+1]);
return f[i][j];
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){ cin>>w[i]; w[i+n]=w[i]; }
dp(1, 2*n);
int ans = 0;
for(int i = 1; i <= n; i++)//扫描每条长度为n的链, 最大值为答案。
ans = max(ans, f[i][i+n-1]);
cout<<ans<<'\n';
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/80404250
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)