CodeForces - 855B. Marvolo Gaunt‘s Ring

一.题意

给定p,q,r以及数组a[n]，求

二.思路

枚举，记录前i个位置的p*a[i]的最大值及后i个位置r*a[i]的最大值然后枚举即可，时间复杂度 ，与acwing 3956.截断数组有几分相似。

三.代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f;
int ans;
int p,q,r,n;
int a[N];
int fst[N],bck[N];
signed main(void){cin >> n >> p >> q >> r;memset(fst,-0x3f,sizeof(fst));memset(bck,-0x3f,sizeof(bck));for(int i = 1;i<=n;i++) scanf("%lld",&a[i]);fst[1] = p*a[1];for(int i = 2;i<=n;i++) fst[i] = max(fst[i-1],p*a[i]);bck[n] = r*a[n];for(int i = n-1;i;i--) bck[i] = max(bck[i+1],r*a[i]);bool step = false;for(int i = 1;i<=n;i++)if(!step || ans<fst[i]+q*a[i]+bck[i]) step = true,ans = fst[i]+q*a[i]+bck[i];cout << ans << endl;return 0;
}