【NOIP2006】【Luogu1063】能量项链

举报
小哈里 发表于 2022/05/10 23:02:00 2022/05/10
【摘要】 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。