CF855B Marvolo Gaunt's Ring 【DP】

Marvolo Gaunt's Ring

Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made.

Value of x is calculated as maximum of p·ai + q·aj + r·ak for given p, q, r and array a1, a2, ... an such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.

Input

First line of input contains 4 integers n, p, q, r ( - 1e9 ≤ p, q, r ≤ 1e9, 1 ≤ n ≤ 1e5).

Next line of input contains n space separated integers a1, a2, ... an ( - 1e9 ≤ ai ≤ 1e9).

Output

Output a single integer the maximum value of p·ai + q·aj + r·ak that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

Examples
input

5 1 2 3
1 2 3 4 5

output

30

input

5 1 2 -3
-1 -2 -3 -4 -5

output

12

Note
In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.

题意

给定一个序列和三个值p,q,r，从序列中找三个值ai,aj,ak，满足1<=i<=j<=k，使得p * ai+q * aj+r * ak值最大

分析

dp[i][j]:前j个元素中选i个值组合成的最大值
i = 1: p * ai
i = 2: p * ai+q * aj
i = 3: p * ai+q * aj+r * ak
状态转移方程：

    i = 1时：不难看出，因为只选一个，那么就是j之前的最大值和arr[i]*p求最大值
            dp[i][j] = max(dp[i][j-1],arr[i]*p)
    i = 2时，需要在选过ai的基础上，选aj，那么对于j这个位置有选与不选两种情况
        不选j：dp[i][j] = dp[i][j-1] 
         选j：dp[i][j] = dp[i-1][j]+arr[i]*q
        然后两者取最大dp[i][j] = max(dp[i][j-1],dp[i-1][j]+arr[i]*q);
    i = 3同理,也是选与不选两种情况：
        dp[i][j] = max(dp[i][j-1],dp[i-1][j]+arr[i]*r);

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;

int N,p,q,r;
ll arr[maxn];
ll dp[4][maxn];
int main(){
    cin>>N>>p>>q>>r;
    for(int i = 1;i<=N;i++) scanf("%lld",&arr[i]);

    dp[1][1] = arr[1]*p;
    dp[2][1] = dp[1][1]+arr[1]*q;
    dp[3][1] = dp[2][1]+arr[1]*r;
    for(int i = 1;i<=3;i++){
        for(int j = 2;j<=N;j++){
            if(i == 1) dp[i][j] = max(dp[i][j-1],arr[j]*p);
            if(i == 2) dp[i][j] = max(dp[i][j-1],dp[i-1][j]+arr[j]*q);
            if(i == 3) dp[i][j] = max(dp[i][j-1],dp[i-1][j]+arr[j]*r);
        }
    }
    cout<<dp[3][N]<<endl;
    return 0;
}