概要

予算 \(K\) の範囲で、隣り合う街路灯を同時に選べないという制約付きで、削減効果の合計（価値）を最大化する問題です。
「一次元上の独立集合（隣接禁止）」＋「ナップサック（予算制約）」を同時に扱います。

考察

この問題の難しさは制約が2種類あることです。

• 予算制約：選んだ街路灯の費用 \(W_i\) の合計が \(K\) 以下（ナップサック）
• 隣接禁止：\(i\) と \(i+1\) を同時に選べない（一次元の隣接制約）

素朴に「選ぶ/選ばない」を全探索すると \(2^N\) 通りになり、\(N \le 200\) では到底間に合いません。

一方、隣接禁止だけなら
\(dp[i] =\)「\(1..i\) まで見て最大価値」
のような典型DPで解けますが、今回はさらに「使った費用」も状態に持つ必要があり、\(i\) 番目を選ぶときに \(i-1\) を選んでいないことも同時に管理しなければなりません。

ここでの重要な気づきは次の通りです：

• 「直前（\(i-1\)）を選んだかどうか」さえ分かれば、隣接禁止は判断できる
  
• 予算は \(K \le 10^4\) なので、費用を状態にした \(O(NK)\) のDPが間に合う

そのため、
「直前を選んでいない状態」と「直前を選んだ状態」の2つに分けたDPを作ると、隣接禁止と予算制約を両立できます。

アルゴリズム

費用の合計を \(c(0 \le c \le K)\) として、次のDPを考えます。

• \(dp0[c]\)：いま見ている位置の「直前の街路灯を選んでいない」状態で、費用合計が \(c\) のときの最大削減効果
• \(dp1[c]\)：いま見ている位置の「直前の街路灯を選んだ」状態で、費用合計が \(c\) のときの最大削減効果

初期状態はまだ何も選んでいないので： - \(dp0[0] = 0\) - その他は不可能状態として \(-\infty\)（コードでは十分小さい値 NEG）にします

街路灯 \((v, w)\) を1つずつ処理し、次の遷移を行います。

1. 今回の街路灯を選ばない

今回選ばないなら、次の「直前未選択」状態に移ります。
直前が選ばれていたかどうか（\(dp0, dp1\)）は関係なく、「今回を選ばない」ので次は必ず未選択状態です。

• \(new0[c] = \max(dp0[c], dp1[c])\)

2. 今回の街路灯を選ぶ

今回を選ぶためには、隣接禁止より「直前は選んでいない」必要があります。
つまり \(dp0\) からしか遷移できません。

• \(new1[c] = dp0[c-w] + v\)（ただし \(c \ge w\)）

これで「直前を選んだ状態」へ移ります。

最後に、全街路灯を処理し終えたら答えは - \(\max_c \max(dp0[c], dp1[c])\) です（最後が選択/非選択どちらでもよい）。

計算量

• 時間計算量: \(O(NK)\)
  （各街路灯ごとに費用 \(0..K\) を走査）
• 空間計算量: \(O(K)\)
  （\(dp0, dp1\) の長さ \(K+1\) の配列を使い、ローリングで更新）

実装のポイント

• 不可能状態を表す値が必要です。コードでは NEG = -10**30 として、到達不可能な状態を区別しています（\(V_i\) が最大でも \(10^9\) で \(N \le 200\) なので十分小さい）。

• 配列更新は ローリング（new0/new1を作って入れ替え）にすると空間が \(O(K)\) で済みます。

• 「選ぶ」遷移は 必ず \(dp0\) からにすることで、隣接禁止を自然に守れます。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    k = int(next(it))

    NEG = -10**30
    dp0 = [NEG] * (k + 1)  # previous not chosen
    dp1 = [NEG] * (k + 1)  # previous chosen
    dp0[0] = 0

    for _ in range(n):
        v = int(next(it))
        w = int(next(it))

        new0 = [NEG] * (k + 1)
        new1 = [NEG] * (k + 1)

        for c in range(k + 1):
            a = dp0[c]
            b = dp1[c]
            new0[c] = a if a >= b else b

        for c in range(w, k + 1):
            prev = dp0[c - w]
            if prev != NEG:
                val = prev + v
                if val > new1[c]:
                    new1[c] = val

        dp0, dp1 = new0, new1

    print(max(max(dp0), max(dp1)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。