B. Marvolo Gaunt’s Ring (递推)

B. Marvolo Gaunt’s Ring

题目链接

大致题意:

给你三个数 p，q，r，然后给你给你一个有序的序列，让你在序列中跳出三个数i,j,k（i <=j<=k）使得 p*a[i]+q*a[j]+r*a[k] 最大,输出最大值

---

解题思路:

网上全是前缀后缀的思想,我的第一思路是递推,没想到AC了

状态表示:

f[pos][0]表示序列枚举到了第pos位,选择了第一个数a[i]后的最大值 p*a[i]

f[pos][1]表示序列枚举到了第pos位,选择了第二个数a[j]后的最大值(当然第一个已经选完) p*a[i]+q*a[j]

f[pos][2]表示序列枚举到了第pos位,选择了第三个数a[k]后的最大值(当然第一个和第二个已经选完) p*a[i]+q*a[j]+r*a[k]

分析:由于i,j,k可以相等,所以每种状态有两个情况转移得来,前i-1个序列当前状态的最大值,和第i位上一状态的最大值

转移方程:

f[i][0] = max(f[i - 1][0], p * a[i])
f[i][1] = max(f[i - 1][1], f[i][0] + q * a[i])
f[i][2] = max(f[i - 1][2], f[i][1] + r * a[i])

补充:因为有负值,初始化f数组为-3e18 (因为a[i]=1e9,q=-1e9 ,乘3就是-3e18 )

---

AC代码:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(a) cout << #a << " = " << a << endl;
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m, k;
ll a[N];
ll f[N][3];
int main(void)  //  dp
{
	ios::sync_with_stdio(0); cin.tie(0);
	ll p, q, r; cin >> n >> p >> q >> r;
	for (int i = 1; i <= n; ++i)cin >> a[i];
	for (int i = 0; i <= n; ++i) f[i][0] = f[i][1] = f[i][2] = -3000000000000000010;
	for (int i = 1; i <= n; ++i) {
		f[i][0] = max(f[i - 1][0], p * a[i]);
		f[i][1] = max(f[i - 1][1], f[i][0] + q * a[i]);
		f[i][2] = max(f[i - 1][2], f[i][1] + r * a[i]);
	}
	ll res = -3000000000000000010;
	for (int i = 1; i <= n; ++i)res = max(res, f[i][2]);
	cout << res << endl;
	return 0;
}

---