実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 621

問題概要

高橋君はこれから $N$ 匹のモンスターに出会い、 $i$ 匹目のモンスターを倒すことで得られる経験値は $A_i$ である。高橋君はそれぞれのモンスターについて逃がすか倒すか選ぶことができ、それぞれの行動によって次のように経験値を得る。

$i$ 匹目のモンスターを逃がした場合、得られる経験値は $0$ である。
モンスターを倒したとき、経験値を $A_i$ 得る。ただし、モンスターを倒すのが偶数回目 (0回は含まない) であるとき、さらに追加で経験値を $A_i$ 得る。

このとき、 $N$ 匹から高橋君が得た経験値の合計としてあり得る最大の値を求めよ。

制約

入力はすべて整数。
$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$

考察

D問題のDは DP のD。

$\mathrm{dp}_{i, 0} :=$ $i$ 匹目までに偶数匹 (0を含む) のモンスターを倒したときに得られる経験値の最大値

$\mathrm{dp}_{i, 1} :=$ $i$ 匹目までに奇数匹のモンスターを倒したときに得られる経験値の最大値

として、2次元の dp テーブルを作り、 $\mathrm{dp}_{0, 0} = 0, \: \mathrm{dp}_{0, 1} = -\infty$ と初期化しておく ( $\mathrm{dp}_{0, 1} = 0$ としてしまうと、0匹倒す場合を含めてしまうことになるので NG) 。

続いて、遷移パターンを考えていく。

$i$ 匹目に偶数匹倒すことになるのは、次の2つの場合である。

$i - 1$ 匹目までに偶数匹倒していて、 $i$ 匹目を逃がす。
$i - 1$ 匹目までに奇数匹倒していて、 $i$ 匹目を倒す (経験値2倍獲得) 。

また同様に、 $i$ 匹目に奇数匹倒すことになるのは、

$i - 1$ 匹目までに偶数匹倒していて、 $i$ 匹目を倒す。
$i - 1$ 匹目までに奇数匹倒していて、 $i$ 匹目を逃がす。

の2つの場合である。

したがって、 $1 \leq i \leq N$ における漸化式は次のようになる。

$\mathrm{dp}_{i, 0} = \max(\mathrm{dp}_{i-1, 0} + 0, \mathrm{dp}_{i-1, 1} + 2A_i)$

$\mathrm{dp}_{i, 1} = \max(\mathrm{dp}_{i-1, 0} + A_i, \mathrm{dp}_{i-1, 1} + 0)$

そして、求めるべき答えは $\max(\mathrm{dp}_{N, 0}, \mathrm{dp}_{N, 1})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr auto INFL = 1LL << 60;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N + 1);
    rep(i, 1, N + 1) cin >> A[i];

    vector<vector<ll>> dp(200020, vector<ll>(2, -INFL));
    dp[0][0] = 0;
    rep(i, 1, N + 1) {
        dp[i][0] = max(dp[i-1][0] + 0, dp[i-1][1] + A[i] * 2);
        dp[i][1] = max(dp[i-1][0] + A[i], dp[i-1][1] + 0);
    }

    cout << max(dp[N][0], dp[N][1]) << endl;
}