A18276. 宝可梦
填空题
困难
知识点
题目描述
宝可梦
题目描述
你将按顺序遭遇 n 只宝可梦，第 i 只宝可梦的强度为 ai。
对每只宝可梦，你可以选择将其放走或击败，收益规则如下：
- 放走宝可梦：获得0点经验值。
- 击败强度为x的宝可梦：基础获得x点经验值；若本次是你第偶数次击败宝可梦（第2次、第4次……），将额外获得x点经验值。
请计算你能获得的最大总经验值。
输入格式
第一行一个正整数n，表示宝可梦的总数量。
第二行n个正整数a1,a2,,,,,an，依次表示每只宝可梦的强度。
输出格式
输出一个整数，表示可获得的最大总经验值。
输入样例
5
1 5 3 2 7输出样例
28说明提示
- 1 ≤ n ≤ 2 *105 ， - 1 ≤ ai ≤ 109
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
ll dp0 = 0, dp1 = -INF;
for (int i = 0; i < n; ++i)
{
ll x;
cin >> x;
ll nd0 = dp0, nd1 = dp1; // 不放走：原样继承
// 选择击败进行状态更新
nd0 = max(nd0, dp1 + 2 * x);
nd1 = max(nd1, dp0 + x);
dp0 = nd0; dp1 = nd1;
}
cout << max(dp0, dp1) << '\n';
return 0;
}
上一题
下一题