abc369 D - Bonus EXP

Jeanny / 2024-09-02 / 原文

一句话题意：
给你一个序列，对每一个数字你可以选择打或者不打，当打的次数为偶数时，奖励翻1倍(2*ai)，奇数时1倍(ai)，不打奖励为0。求最大得分。

我真的傻叉了。。。第二维表示奇偶性f[][]，而我一开始表示当前位置打不打。。。

#include<bitsstdc++.h>
#include<climits>
#define int long long
using namespace std;
int n, a[200005], g[200005][3],f[200005][3];
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; for(int i = 1; i <= n; i++) cin>>a[i]；
    f[0][0] = 0;
    f[0][1] = LONG_LONG_MIN; 
	for(int i = 1; i <= n; i++) {
		f[i][1] = max (f[i - 1][1], f[i - 1][0] + a[i]);
		f[i][0] = max (f[i - 1][0], f[i - 1][1] + a[i] * 2);
	} 

    cout<<max(f[n][0], f[n][1])<<endl;
    return 0;
}

以下是我s的代码

// for(int i = 1; i <= n; i++){     
    //     if(g[i-1][1] % 2 == 1){//ji
    //         if(f[i-1][1] + 2 * a[i] > f[i][1]){
    //             f[i][1] = f[i-1][1] + 2 * a[i];
    //             g[i][1] = g[i-1][1] + 1;
    //         }
    //         if(f[i-1][1] > f[i][0]){
    //             f[i][0] = f[i-1][1];
    //             g[i][0] = g[i-1][1];
    //         }  
    //     }
    //     if(g[i-1][1] % 2 == 0){//ou
    //         if(f[i-1][1] + a[i] > f[i][1]){
    //             f[i][1] = f[i-1][1] + a[i];
    //             g[i][1] = g[i-1][1] + 1;
    //         }
    //         if(f[i-1][1] > f[i][0]){
    //             f[i][0] = f[i-1][1];
    //             g[i][0] = g[i-1][0];
    //         }
    //     }
    //     if(g[i-1][0] % 2 == 1){//上一个没打，到i-1是奇数
    //         if(f[i-1][0] + 2 * a[i] > f[i][1]){
    //             f[i][1] = f[i-1][0] + 2 * a[i];
    //             g[i][1] = g[i-1][0] + 1;

    //         }
    //         if(f[i-1][0] > f[i][0]){
    //             f[i][0] = f[i-1][0];
    //             g[i][0] = g[i-1][0];
    //         }
    //     }
    //     if(g[i-1][0] % 2 == 0){//上一个没打，到i-1是偶数
    //         if(f[i-1][0] + a[i] > f[i][1]){
    //             f[i][1] = f[i-1][0] + a[i];
    //             g[i][1] = g[i-1][0] + 1;
    //         }
    //         if(f[i-1][0] > f[i][0]){
    //             f[i][0] = f[i-1][0];
    //             g[i][0] = g[i-1][0];
    //         }
    //     }
    // }
    // cout<<f[4][0]<<endl;
    // cout<<g[4][0]<<endl;