题解：AT_abc369_d [ABC369D] Bonus EXP

xxr___ · 2024-09-01 13:31:10 · 题解

思路：

提供一个不一样的思路，不难发现，最优策略肯定不会连续两个及以上都不打，因为如果放弃两个的话，不如把这两个都选上，这样奇偶性也是不变的，换句正常点的话说，每次只会丛前一个或者是前前一个转移。

转移：

设 dp_{i,0} 表示第 i 个结束后，此时选了偶数个的最优策略，设 dp_{i,1} 表示第 i 个结束后，选了奇数个的最优策略，答案就是 \max(dp_{n,1},dp_{n,0})。

代码：

#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
const int N=2e5+5;
#define int long long
int dp[N][3],n,a[N];
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    up(i,1,n) cin>>a[i];
    dp[1][1]=a[1];
    dp[1][0]=0;
    up(i,2,n){
        dp[i][0]=max(dp[i-1][1]+a[i]+a[i],dp[i-2][1]+a[i]+a[i]);
        dp[i][1]=max(dp[i-1][0]+a[i],dp[i-2][0]+a[i]);
    }
    cout<<max(dp[n][0],dp[n][1]);
    return 0;
}