题解：B4135 [信息与未来 2014] 取数

· · 题解

主要思路

考虑 dp，创建 dp[N][2]。

  1. 状态定义：dp_{i,0} 表示考虑前 i 个数，并且 x_{i} 不选的取数和最大值；dp_{i,1} 表示考虑前 i 个数，并且 x_{i} 选的取数和最大值。
  2. 状态转移：对于 x_{i} 不选，则取 dp_{i-1,0} 与 dp_{i-1,1} 的最大值即可；反之，在 i \neq 1 的情况下，则 x_{i-2} 是一定不能选的，且 x_{i-1} 是一定要选的，由于只考虑前 i 个数，所以选 x_{i} 和 x_{i+1} 的情况不需要考虑，转移方程即： dp_{i,1}=dp_{i-2,0}+x_{i-1}+x_{i}
  3. 初始值：不选数总和即 0，所以默认 0 即可。
  4. 答案：题目求得是在这 n 个数内的取数和最大值，就是 dp_{n,0} 与 dp_{n,1} 里取最大值。

时间复杂度

O(n)

注意事项

由于 n \cdot x_{i} 的最大值到达了 10^{14}，所以十年 OI 一场空，_____。

AC Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
int x[N];
ll dp[N][2];
// ----------------------------

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    // ----------------------------
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        if (i > 1) dp[i][1] = dp[i - 2][0] + x[i - 1] + x[i];
    }
    // ----------------------------
    cout << max(dp[n][0], dp[n][1]);
    return 0;
}