能量项链

博客破百祭!!!

题目链接

https://www.luogu.com.cn/problem/P1063

解题思路

一道十分类似的题
成环已经不是难点了吧,化环为链。
与上面那个题不同的是这个题两个数也可以操作,因为是俩珠子,形如珠子1(10,2) 珠子2(10,2),最大的得分为10*2*10=200 > 2*10*2=40,显然上面那个题只能对至少三个珠子操作吧。
dp的含义依旧是取走i,j之间的全部数,得到的最大值。
本质上的区别在于本题可以取数取到只剩一个数,那我们把最长区间取到长度为n+1,最后输出长度为n+1的区间中的最大值,而且最小区间长度可以为2。
当区间长度取到n+1的时候,a[i]==a[j],这就相当于实现了取到只剩一个数的操作,
举个例子:10 3 2 10 3 2i=1,j=4时,相当于把3留下与两端的10合并,或者把2留下与两端的10合并,最后相当于就剩了个10。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
ll dp[N<<1][N<<1],a[N<<1],n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }

    for(int len=2;len<=n+1;len++)//注意范围
        for(int i=1;i+len-1<=n+n;i++){
            int j=len+i-1;
            for(int k=i+1;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
        }

    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i][i+n]);//注意dp的第二维

    cout<<ans<<endl;
} 
dp 文章被收录于专栏

全部评论

相关推荐

喜欢吃蛋糕仰泳鲈鱼是我的神:字节可以找个hr 给你挂了,再放池子捞
点赞 评论 收藏
分享
铁锈不腻玩家:下面那个袁先生删了,问他怎么回事,头像都换不明白
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务