Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n,p,q,r，以及n（1E5）个数，所有数的范围都是[-1E9,1E9]，现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n
思路：傻逼dp…
我。。好菜啊。。。万年dp苦手。
直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。
dp[i][0] stores maximum of value p·a__x for x between 1 and i. Similarly dp[i][1] stores the maximum value of p·a__x + q·a__y such that x ≤ y ≤ i and dp[i][2] stores maximum value of p·a__x + q·a__y + r·a__z for x ≤ y ≤ z ≤ i.
To calculate the dp:
dp[i][0] = max(dp[i - 1][0], p·a__i)
dp[i][1] = max(dp[i - 1][1], dp[i][0] + q·a__i)
dp[i][2] = max(dp[i - 1][2], dp[i][1] + r·a__i)
The answer will be stored in dp[n][2]
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月25日 星期一 19时26分34秒
4File Name :B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35LL a[N];
36LL p,q,r;
37int n;
38LL dp[N][3];
39int main()
40{
41#ifndef ONLINE_JUDGE
42 freopen("./in.txt","r",stdin);
43#endif
44 cin>>n>>p>>q>>r;
45 for ( int i = 1 ; i <= n ; i++) cin>>a[i];
46 LL ans = 1LL<<60;
47 ans*=-5LL;
48 ms(dp,0xc0);
49 //重要的是维护一个前缀最大值。
50 for ( int i = 1 ; i <= n ; i++)
51 dp[i][0] = max(dp[i-1][0],p*a[i]);
52 for ( int i = 1 ; i <= n ; i++)
53 dp[i][1] = max(dp[i-1][1],dp[i][0]+q*a[i]);
54 for ( int i = 1 ; i <= n ; i++)
55 dp[i][2] = max(dp[i-1][2],dp[i][1]+r*a[i]);
56 cout<<dp[n][2]<<endl;
57
58#ifndef ONLINE_JUDGE
59 fclose(stdin);
60#endif
61 return 0;
62}