AtCoder Beginner Contest 162 F - Select Half

きれいな実装をします。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 0x1fffffffffffffff;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(auto& i : a) cin >> i;
    const ll skip = 1 + n % 2;

    // 取る 取らない 取る 取らない ... を貪欲にやっていくと 1 + n % 2 個余って、
    // 1 + n % 2 回飛ばせることがわかる

    vector<vector<ll>> dp(n + 2, vector<ll>(skip + 1, -INF));

    // dp[i][j] := a[0, i) を j 要素無視して1つ飛びに取ったときの最大値

    dp[0][0] = 0;
    for(ll i = 0; i <= n; i++) for(ll j = 0; j <= skip; j++){
        if(j < skip) chmax(dp[i + 1][j + 1], dp[i][j]);
        if(i < n) chmax(dp[i + 2][j], dp[i][j] + a[i]);

        // 1個選んだら1個選ばないのもセット

    }
    cout << dp[n + 1][skip] << endl;

    // なので floor(n / 2) * 2 + skip == n + 1 に答えが入る

}