ABC219D - Strange Lunchbox

配るDPでないと，うまく書けない例？
【類題】

• ABC099C - Strange Bank - 競プロはじめました

ナップサック問題に雰囲気が似ている：D - Knapsack 1 - 競プロはじめました

DP

考え方

$N$コの弁当からたこ焼き$X$コ・たい焼き$Y$コ（ぴったり）になるよう選ぶ方法の数を$f(N,X,Y)$とする（*1）．$0 \leq n \leq N - 1$，$0 \leq x \leq X - 1$，$0 \leq y \leq Y- 1$について$f(n,x,y)$がわかれば，$f(N,X,Y)$が計算できる．よって，$f(N,X,Y)$はDPで求められる．求める答えは

\begin{aligned}
\min\{f(N, x, y) \mid x \geq X, y\geq Y \}
\tag{1}
\end{aligned}

となる．

ここで，遷移は，$N$コ目の弁当を選ばない場合と選ぶ場合を考えて，
【貰うDP】

\begin{aligned}
f(n,x,y)
=\min\{ f(n - 1, x, y), f(n - 1, x - A_{i}, y - B_{i}) + 1 \}
\end{aligned}

【配るDP】

\begin{aligned}
\begin{cases}
\, f(n + 1, x, y) = \min\{f(n + 1, x, y), f(n, x, y)\} \\
\, f(n + 1, x + A_{i}, y + B_{i})
=\min\{f(n + 1, x + A_{i}, y + B_{i}), f(n, x, y) + 1 \}
\end{cases}
\end{aligned}

である（ただし，$i = 1,2,...,N -1$は可能な範囲をすべて動く）．

「配るDP」の場合，$x \geq X$となるものは$x = X$に置き換え，$y \geq Y$となるものは$y = Y$に置き換えれば，式$(1)$を更新操作に統合できる．

以下，$f(n,x,y)$をdp[n][x][y]で表す．

貰うDP

dp[i][x][y]に遷移させるように更新する．

うまく書けない．．．

配るDP

dp[i][x][y]から遷移するように更新する．

INF = 1000

N = int(input())
X, Y = map(int, input().split())
bento = [tuple(map(int, input().split())) for i in range(N)]
  
dp = [[[INF] * (Y + 1) for _ in range(X + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
  A, B = bento[i]
  for j in range(X + 1):
    for k in range(Y + 1):
      dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
      dp[i + 1][min(j + A, X)][min(k + B, Y)] = min(dp[i + 1][min(j + A, X)][min(k + B, Y)], dp[i][j][k] + 1)

print(dp[N][X][Y] if dp[N][X][Y] < INF else -1)

*1:「$X$以上・$Y$以上となる最小の個数」と考えても，遷移・初期化含めて全く同じ形になる．