SoundHound Inc. Programming Contest 2018 Masters Tournament 本戦 B - Neutralize

B - Neutralize

問題概要

N個の整数値からなる数列$ b = \{ b_1, b_2, \cdots b_n \} $について，連続するK個の要素を全て0にするという操作を好きなだけ繰り返して良いとき，数列に含まれる値の和を最大化する．

($ 1 \leq K \leq N \leq 10^5$)

解法概要

最初は貪欲にやってみたけど無理っぽいのでDPを考える．

dp[i]をi番目まで見たときの (問題の条件を満たしているときの) 和の最大値とすると，次のような遷移のパターンが考えられる．

• i > kのとき

  • 直前までの最大値にさらに$ b_i$を足す ($ dp[ i-1 ] + b_i $)
  • 直前のk個の値は確実に使わない (i-k-1番目までの最大値を使う) が，$ b_i$は使う
  • $ b_i$を含む，今まで見た最新k個の値は使わない ($ dp[k]$から$ dp[i-1]$までの最大値)

• i <= kのときは$ b_i$の値を足していくしかなさそう

最大値は必要になるたびに求めていると間に合わないので，dp用配列とは別に最大値用配列を用意して毎回更新していけば良さそう．

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int main(){
    int n,k;
    cin >> n >> k;

    ll b, dp[n+1], max_[n+1];
    dp[0] = 0;
    max_[0] = 0;
    for(int i=1;i<=n;i++){
        cin >> b;
        if(i <= k){
            dp[i] = dp[i-1] + b;
        }else{
            dp[i] = max({max_[i-k], max_[i-k-1]+b, dp[i-1]+b});
        }
        max_[i] = max(max_[i-1], dp[i]);
    }

    cout << max(max_[n-k], dp[n]) << endl;
}

感想

久々に400点問題に苦戦した．DPの遷移をコンテスト時間内に思いついたことがないかもしれないくらいDPが苦手すぎる．