【CF Manthan, Codefest 17 B】Marvolo Gaunt's Ring

阅读: 评论:0

【CF Manthan, Codefest 17 B】Marvolo Gaunt's Ring

【CF Manthan, Codefest 17 B】Marvolo Gaunt's Ring

【链接】h在这里写链接


【题意】


给你n个数字; 让你在其中找出三个数字i,j,k(i<=j<=k); 使得p*a[i]+q*a[j]+r*a[k]最大;

【题解】


/*
    有一个要求i<=j<=k;
    也就是说系数之间的下标是有关系的。
    枚举第一个位置的下标i;
        则第二个人j
        i<=j<n
        枚举中间那个人的位置在哪。
    求出前i个位置,第一个人能获得的最大值是多少
    求出后n-i个位置,第三个人能获得的最大值是多少
*/

【错的次数】


1

【反思】


一开始并没有注意到顺序的作用。 hack点是:很多人的初始化不够小. 1 1e9 1e9 1e9 -1e9 这组数据过不了

【代码】

#include <bits/stdc++.h>
#define LL long long
using namespace std;const int N = 1e5;int n;
LL pre[N+10],after[N+10];//前缀最大,后缀最大
LL a[N+10],p,q,r;int main()
{//freopen("F:\", "r", stdin);scanf("%d%lld%lld%lld", &n, &p, &q, &r);for (int i = 1;i <= n;i++)scanf("%lld",&a[i]);pre[1] = p*a[1];for (int i = 2;i <= n;i++) pre[i] = max(pre[i-1],p*a[i]);after[n] = r*a[n];for (int i = n-1;i >= 1;i--) after[i] = max(after[i+1],r*a[i]);LL ans = pre[1]+after[1]+q*a[1];for (int i = 2;i <= n;i++)ans = max(ans,pre[i]+after[i]+q*a[i]);printf("%lldn",ans);return 0;
}


本文发布于:2024-01-28 07:37:03,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/17063986255840.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:Codefest   Manthan   CF   Ring   Gaunt
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23