Skip to content

CF369D Bonus EXP

原题链接：D - Bonus EXP

Tag：DP

题目描述

高桥君遇到了 \(N\) 只怪物，依次遇到每一只怪物，第 \(i\) 只怪物的强度为 \(A_i\)。

高桥君可以选择对每只怪物是放走还是击败。
高桥君通过以下的方式获得经验值：

  • 如果选择放走怪物，获得的经验值为 \(0\)。
  • 如果击败强度为 \(X\) 的怪物，他可以获得 \(X\) 的经验值。但是，如果这是他第偶数次击败怪物（即第 \(2\) 次、第 \(4\) 次、……），他将额外获得 \(X\) 的经验值。

请计算高桥君通过击败怪物可以获得的最大总经验值。

数据说明：

  • \(1 \leq N \leq 2 \times 10^5\)
  • \(1 \leq A_i \leq 10^9\)

分析

首先看到题，很显然可以使用 \(\text{DP}\) 来做， 我们可以设计一个 \(dp[i][0/1]\) 其意义为： 当第 \(i\) 个怪物为我们第偶数个、奇数个击杀时获得的经验， \(0\) 代表是第偶数个， \(1\) 代表是第奇数个。

之后这里有一个显然的性质， 就是我们无论是在转移 \(dp[i][1]\) 还是 \(dp[i][0]\) 的时候， 最优的情况一定不会出现中间连续有两个不选。 这个的意思是，假设第 \(i\) 个我们必须要放到奇数位或者偶数位来选， 那么这个时候我们实际上是不用从 \(i - 3\) 去转移的， 因为中间这两个一定存在一种方法， 选一个或者选两个来调整第 \(i\) 个作为奇数位还是偶数位。 因此我们转移的时候不必考虑 \(i-3\)， 只需从 \(i-1\) 和 \(i-2\) 开始转移， 具体转移为：

\(\begin{cases} dp_{i,0} = \max(dp_{i-1,1},dp_{i-2,1}) + a_i * 2 \\ dp_{i,1} = \max(dp_{i-1,0},dp_{i-2,0}) + a_i \end{cases}\)

代码实现

void NeverSayNever() {
    int n; cin >> n;
    vector<int> vec(n + 1);
    for (int i = 1; i <= n ; ++i) {
        cin >> vec[i];
    }
    //dp[i][0/1] 表示第 i 只怪物是 0(偶数) 1(奇数) 击败时获得的最大经验
    vector<vector<int>> dp(n+1,vector<int>(2,0));
    dp[1][0] = 0;
    dp[1][1] = vec[1];
    for (int i = 2; i <= n ; ++i) {
        dp[i][0] = max(dp[i-1][1],dp[i-2][1]) + vec[i] * 2;
        dp[i][1] = max(dp[i-1][0],dp[i-2][0]) + vec[i];
    }
    cout << max(dp[n][1],dp[n][0]) << endl;
}

日志

本页面创建于 2024/09/20 20:24