B - Neutralize

問題概要

個の数列が与えられる。個の連続する数字を選んで0にできる。の最大値を求めよ。
B - Neutralize

解法

動的計画法。
が最大値となる数列に含まれるか、あるいは0になるか二通り存在するので、
番目の数字を使った時までの最大値
番目の数字を使わない場合の最大値
とする。
更新は
番目の数字を使うとすると、直前まで0になった場合が存在するので

同様に、使わなかった場合と、の数字を含めてちょうど個の数字を使った場合があるので

最初状態が3通り(使う、0になる列に含まれる、使わない)だと思ってたんですが、使う場合と使われない場合だけで漸化式を書けてしまってアって感じでした。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
using namespace std;
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
signed main(){
    int n; int k;
    cin >> n >> k;
    auto dp = vectors(2,n,-INF);
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    dp[0][0] = v[0]; dp[1][k-1] = 0LL;
    rep(x,n){
        if(x){
            dp[0][x] = max(dp[0][x-1], dp[1][x-1]) + v[x] ;
            if(x-k>=0)dp[1][x] = max(dp[1][x-1],dp[0][x-k]);
        }
    }
    cout << max(dp[0][n-1],dp[1][n-1]) << endl;
}