题目大意
给定 \(n,p,q,r\),并且给出 \(n\) 个数。
在这些数中找 \(i,j,k(1\le i\le j\le k\le n)\),求出 \(\max\{p\times a_i+q\times a_j+r\times a_k\}\)。
题目分析
一道小清新 \(\rm DP\) 题。
设 \(dp[idx][0]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i\}(1\le i\le idx)\)。
\(dp[idx][1]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i+q\times a_j\}(1\le i\le j\le idx)\)。
\(dp[idx][2]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i+q\times a_j+r\times a_k\}(1\le i\le j\le k\le idx)\)。
于是顺推即可:
\(dp[idx][0]=\max\{dp[idx-1][0],p\times a_i\}\)
\(dp[idx][1]=\max\{dp[idx-1][1],dp[idx][0]+q\times a_i\}\)
\(dp[idx][2]=\max\{dp[idx-1][2],dp[idx][1]+r\times a_i\}\)
初始化:
-
\(dp[idx][0]=p\times a_1\)
-
\(dp[idx][1]=p\times a_1+q\times a_1\)
-
\(dp[idx][2]=p\times a_1+q\times a_1+r\times a_1\)
最后答案就是 \(dp[n][2]\)。
时间复杂度为 \(\operatorname{O}(N)\)。
注意开 \(\rm long~long\)。
代码
//2021/11/14
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#define int long long
#define enter() putchar(10)
#define debug(c,que) cerr<<#c<<" = "<<c<<que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;
#define speed_up() std::ios::sync_with_stdio(false)
namespace Newstd
{
inline int read()
{
char c;
bool flag=false;
while((c=getchar())<'0' || c>'9')
{
if(c=='-') flag=true;
}
int res=c-'0';
while((c=getchar())>='0' && c<='9')
{
res=(res<<3)+(res<<1)+c-'0';
}
return flag?-res:res;
}
inline void print(int x)
{
if(x<0)
{
putchar('-');x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+'0');
}
}
using namespace Newstd;
using namespace std;
const int ma=100005;
int a[ma];
int dp[ma][3];
/*
dp[i][0]:前 i 个数中取 p*a_i 最大值
dp[i][1]:前 i 个数中取 p*a_i+q*a_j 最大值
dp[i][2]:前 i 个数中取 p*a_i+q*a_j+r*a_k 最大值
*/
int n,p,q,r;
#undef int
int main(void)
{
#define int long long
n=read(),p=read(),q=read(),r=read();
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
dp[1][0]=p*a[1];
for(register int i=2;i<=n;i++)
{
dp[i][0]=max(dp[i-1][0],p*a[i]);
}
dp[1][1]=p*a[1]+q*a[1];
for(register int i=2;i<=n;i++)
{
dp[i][1]=max(dp[i-1][1],dp[i][0]+q*a[i]);
}
dp[1][2]=p*a[1]+q*a[1]+r*a[1];
for(register int i=2;i<=n;i++)
{
dp[i][2]=max(dp[i-1][2],dp[i][1]+r*a[i]);
}
printf("%lld\n",dp[n][2]);
return 0;
}