问题陈述

高桥将按顺序遇到 $N$ 怪物。第 $i$ 个怪物 $(1\leq i\leq N)$ 的力量为 $A$ 。
对于每一个怪物，他可以选择让它离开或击败它。
每个行动奖励他的经验值如下：
-如果他放走了怪物，他将获得 $0$ 经验值。
-如果他击败了一个力量为 $A$ 的怪物，他将获得 $A$ 经验值。
如果它是一个被击败的偶数怪物(第2，第4，..)，他将获得额外的 $A$ 经验值。找出他可以从 $N$ 怪物获得的最大总经验值。

约束

—$1\leq N\leq 2\times 10^5$
—$1\leq A_i\leq 10^9$
—所有输入值均为整数。

思路：虽然一开始想到了DP，但是想的是背包DP，由于不能很好的找到背包问题中对应的容量和价值，所以我又去想了DFS，但由于时间复杂度太高，49个测试只过了4个T~T。

后面去看了题解，看到还是要用DP，用来记录每一个怪物被第偶数次捕捉获得的总经验f_even和第奇数次捕捉获得的总经验f_odd，最后再求max就得到最优解max(f_even, f_odd)

要注意：f_odd要初始化为负无穷，避免在第一次捕捉怪物后f_even比f_odd大

状态表示f[i]:

集合:所有只从前i个怪物中捕捉获得的经验值的集合

属性：Max

状态转移方程：

第偶数次捕捉：f_even = max(f_even, f_odd + 2 * a)

第奇数次捕捉：f_odd = max(f_odd, f_even + a)

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 200010, INF = 0x3f3f3f3f;
int n;

int main()
{
    scanf("%d", &n);

    LL f_even = 0, f_odd = -INF; // f_even 为击败第偶数个怪物，f_odd为击败第奇数个怪物
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);

        LL tmp = f_even;
        f_even = max(f_even, f_odd + 2 * a);
        f_odd = max(f_odd, tmp + a);
    }

    cout << max(f_even, f_odd) << endl;
    return 0;
}