Strange Lunchbox [サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219） D]

https://atcoder.jp/contests/abc219/tasks/abc219_d

前提知識

• DP

解説

https://atcoder.jp/contests/abc219/submissions/26483767

あまりピンとこないかもしれないがDPで解ける。
初手でDPが思いついて試すとできたので、DPに至る過程は説明できない…

DP

dp[i][tako][tai] := i番目の弁当まで買うかが確定していて、これまでのたい焼きの個数がtaiで、たこ焼きの個数がtakoである最小弁当個数

これで解く。重要な部分が、X,Y≦300であるという部分である。
状態として、たい焼き・たこ焼きの個数はX,Yより大きくなりうるが、X以上である個数は条件としてはすべて同一視しても問題ない。
よって、Xより大きい個数はすべてXであると丸めてしまうことにすると、たい焼き、たこ焼きの個数は0～X/Yということになる。
この前提を考えると、DPの状態数は300×300×300通りくらいになるので、状態数的にはメモリ/計算量に収まる。
これは、上限を適切に指定して丸めることで間に合うというテクであり、DPを行う上で状態を丸める良い手法である。

あとは？

後は頑張って実装するだけ。
上限を指定する場合は更新時にminを使って超えたら最大値に置き換えるという感じにすると分岐が減って見栄えがいい。

int N, X, Y;
int A[301], B[301];
int dp[301][301][301];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X >> Y;
    rep(i, 0, N) cin >> A[i] >> B[i];

    rep(i, 0, N + 1) rep(tako, 0, 301) rep(tai, 0, 301) dp[i][tako][tai] = inf;
    dp[0][0][0] = 0;
    rep(i, 0, N) rep(tako, 0, X + 1) rep(tai, 0, Y + 1) if (dp[i][tako][tai] < inf) {
        chmin(dp[i + 1][tako][tai], dp[i][tako][tai]);
        chmin(dp[i + 1][min(tako + A[i], X)][min(tai + B[i], Y)], dp[i][tako][tai] + 1);
    }

    int ans = dp[N][X][Y] < inf ? dp[N][X][Y] : -1;
    cout << ans << endl;
}