题解：AT_abc369_d [ABC369D] Bonus EXP

· · 题解

[ABC369D] Bonus EXP

题意

有 N 个怪物，打败第 i 个怪物能获得 a_i 的经验，如果第 i 个怪物是第偶数次打败的，经验乘二，求最大经验。

思路

看到题目第一眼肯定是爆搜，但 N 是 2 \times 10^5，暴力无法通过。

经思考发现可以用动态规划做。先设状态，我们设 dp_{i,1} 为当第 i 个数作为第奇数个去选择的最大价值，反之设 dp_{i,2} 为当第 i 个数作为第偶数个去选的最大价值。

再推方程。经过思考，当前这个数作为奇数去选的最大价值是由上一个数作为偶数的最大价值加上当前数的价值与上一个数作为奇数选的最大价值的最大值，简化一下，缩减为下面这个式子：

dp_{i,1}= \max(dp_{i-1,2}+a_i,dp_{i-1,1})

同时偶数奕然：

dp_{i,2}= \max(dp_{i-1,1}+a_i \times 2,dp_{i-1,2})

初始化时把 dp_{0,1} 初始化为负无穷，dp_{0,2} 初始化为 0，因为第一个数只能作为奇数选。

AC代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,a[200005],dp[200005][5];
signed main()
{
    FAST
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[0][1]=-1e18,dp[0][2]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i][1]=max(dp[i-1][1],dp[i-1][2]+a[i]);
        dp[i][2]=max(dp[i-1][1]+a[i]*2,dp[i-1][2]);
    }
    cout<<max(dp[n][1],dp[n][2]);
    return 0;
}