概要

「今どの部屋まで見たか」と「現在持っている荷物数」を状態にした動的計画法（DP）で、条件（荷物数 \(\le K\)、最後に荷物数 \(0\)）を満たしつつ報酬合計の最大値を求める問題です。

考察

重要なのは、将来の選択に影響する情報が 現在の荷物数だけ だという点です。
各部屋で「引き受ける / 断る」を選ぶとき、過去にどの仕事を選んだかの詳細は不要で、「いま荷物を何個持っているか」だけ分かれば次の遷移が決まります。

なぜ全探索は無理か

各部屋で 2 択なので、素朴には \(2^N\) 通り。
\(N\) は最大 \(10^5\) なので到底間に合いません。

DPの発想

dp[c] = ここまで見たとき、荷物数が c の状態で得られる最大報酬
と置けば、各仕事に対して次のように遷移できます。

• 断る: 荷物数は変わらない（報酬も増えない）
• 積む仕事 \((T_i=1)\) を引き受ける: \(c \to c+1\)（ただし \(c+1 \le K\)）、報酬 \(+A_i\)
• 降ろす仕事 \((T_i=0)\) を引き受ける:
  • \(c=0\) なら \(0 \to 0\)（荷物は減らない）、報酬 \(+A_i\)
  • \(c\ge1\) なら \(c \to c-1\)、報酬 \(+A_i\)

この更新を部屋 1 から順に行えば、最終的に dp[0] が答えです（最後に荷物数 0 条件）。

アルゴリズム

1. 長さ \(K+1\) の配列 dp を用意し、初期値は
   • dp[0] = 0（最初は荷物 0、報酬 0）
   • それ以外は到達不能を表す非常に小さい値 NEG
2. 各部屋の仕事 \((t,a)\) を順に処理する。
3. ndp = dp[:] として、まず「断る」遷移を表現する。
4. 仕事を引き受ける遷移を追加:
   • t == 1（積む）:
     • 各 c=0..K-1 について、dp[c] から ndp[c+1] を dp[c]+a で更新
   • t == 0（降ろす）:
     • c=0 から 0 へ +a
     • 各 c=1..K について、dp[c] から ndp[c-1] を dp[c]+a で更新
5. dp = ndp に置き換える。
6. 全部屋処理後、dp[0] を出力。

この実装は、各部屋で荷物数 \(0..K\) の状態だけ見ればよいので効率的です。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(K)\)

（制約に \(NK \le 10^7\) があるため実用的）

実装のポイント

• 到達不能状態を NEG で管理し、そこからの遷移は無視する。

• 同じ部屋内での多重更新の影響を避けるため、ndp を dp のコピーで作る（1ステップ先配列）。

• 降ろす仕事で c=0 の特殊遷移（荷物は減らないが報酬は得る）を忘れない。

• 最後に出すのは dp[0] のみ（「最後に荷物数 0」の条件）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    jobs = [tuple(map(int, input().split())) for _ in range(N)]

    NEG = -10**30
    dp = [NEG] * (K + 1)
    dp[0] = 0

    for t, a in jobs:
        ndp = dp[:]  # skip this job
        if t == 1:
            # take load job: c -> c+1 (if <= K)
            for c in range(K):
                v = dp[c]
                if v != NEG:
                    nv = v + a
                    if nv > ndp[c + 1]:
                        ndp[c + 1] = nv
        else:
            # take unload job:
            # c=0 -> 0 (reward gained)
            if dp[0] != NEG:
                v0 = dp[0] + a
                if v0 > ndp[0]:
                    ndp[0] = v0
            # c>=1 -> c-1 (reward gained)
            for c in range(1, K + 1):
                v = dp[c]
                if v != NEG:
                    nv = v + a
                    if nv > ndp[c - 1]:
                        ndp[c - 1] = nv
        dp = ndp

    print(dp[0])

if __name__ == "__main__":
    main()

---

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