SoundHoundコン本戦-B:Neutralize

問題

https://beta.atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b

長さ N の数列  a_0, a_1, ..., a_{N-1} が与えられる。以下の操作を何回か実施して、 \displaystyle \sum_{i=0}^{N-1} a_i を最大値を求めよ。

  • 操作
    連続する長さ k区間の要素  [a_i, a_{i+k-1}] をすべて 0 にする。

考え方

なるべく a_i \lt 0 の要素を 0 にしたいが、左から順番に貪欲に見ていく方法はうまくいかない。長さ k区間について要素をすべて 0 にできるので、 i について考えるときに i - k の取りうる最大値の状態と比較したい。よってDPをする。

dp[i] := [0, i] の和の値
max[i] := [0, i] の和として取りうる最大値

dpの遷移については、

dp[i] : max(dp[i-1] + b[i], max[i-k])
max[i] : max(dp[i], max[i-1])

となる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), k = in.nextInt();
            long[] b = new long[n+1];
            for (int i = 1; i < n+1; i++) {
                b[i] = in.nextLong();
            }

            long[] dp = new long[n+1];
            long[] max = new long[n+1];

            Arrays.fill(dp, Long.MIN_VALUE/3);
            dp[0] = 0;

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

            out.println(dp[n]);
        }

ポイント

  • 前の状態を保存して、あとで評価する。状態を保存しておきたいのでDP。

類題

雑記

dp の遷移を考えるときに dp[i] は max(dp[i-1] + b[i], dp[i-k]) で問題ないと思っていたが、後ろの i をすべて足さないという場合が考慮できない。最大値を保存しておくのがポイント。