atcoder beginner contest 219 D問題　配るDPが更新されない

前提・実現したいこと

ABC219D問題を解いたのですが、以下のコードを試したところ答えがINFの値のままで更新されません。今回配るDPが模範解答で使われていたので、貰うDPでも試したのですが、なぜ貰うDPでは不正解になるのかわかりません。原因を教えていただけると幸いです。

発生している問題・エラーメッセージ

入力サンプル
3
5 6
2 1
3 4
2 3
を与えると、2と返すべきところと-1と返してしまう。

該当のソースコード

C++
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef long double ld;
5
6const int INF = 1e9;
7
8template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
9template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
10template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}
11
12class Dsu{
13public:
14    vector <ll> par; 
15    vector <ll> siz; 
16
17    Dsu(ll sz_): par(sz_), siz(sz_, 1LL) {
18        for (ll i = 0; i < sz_; ++i) par[i] = i; 
19    }
20    void init(ll sz_) {
21        par.resize(sz_);
22        siz.assign(sz_, 1LL); 
23        for (ll i = 0; i < sz_; ++i) par[i] = i; 
24    }
25
26    ll find(ll x) { 
27        while (par[x] != x) {
28            x = par[x] = par[par[x]]; 
29        }
30        return x;
31    }
32
33    bool merge(ll x, ll y) {
34        x = find(x);
35        y = find(y);
36        if (x == y) return false;
37        if (siz[x] < siz[y]) swap(x, y);
38        siz[x] += siz[y];
39        par[y] = x;
40        return true;
41    }
42
43    bool issame(ll x, ll y) { 
44        return find(x) == find(y);
45    }
46
47    ll size(ll x) { 
48        return siz[find(x)];
49    }
50};
51int N, X, Y;
52vector<int> A, B;
53vector<vector<vector<int>>> dp;
54int main(){
55    ios::sync_with_stdio(false);
56    cin.tie(0);
57    cin >> N >> X >> Y;
58    A.resize(N); 
59    B.resize(N);
60    for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
61    dp.assign(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, INF)));
62    dp[0][0][0] = 0;
63    for(int i = 0; i < N; ++i){
64        for(int j = 0; j <= X; ++j){
65            for(int k = 0; k <= Y; ++k){
66                if(j - A[i] >= 0 && k - B[i] >= 0){
67                    dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - A[i]][k - B[i]] + 1);
68                }
69                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
70            }
71        }
72    }
73    cout << (dp[N][X][Y] == INF ? -1 : dp[N][X][Y]) << endl;
74}

###試したこと(追記:10/1)
この方のコードを参考にし、以下のような配列の再利用を使わず貰うDPを作成しました。するとACされたのですが、元のコードとやっていることが同じに見えるのですが、なぜ結果が異なるのでしょうか。その点も教えていただけると幸いです。

C++
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef long double ld;
5
6const int INF = 1e9;
7
8
9int N, X, Y;
10vector<int> A, B;
11vector<vector<vector<int>>> dp;
12int main(){
13    ios::sync_with_stdio(false);
14    cin.tie(0);  
15    cin >> N >> X >> Y;
16    A.resize(N); 
17    B.resize(N);
18    for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
19    dp.assign(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, INF)));
20    dp[0][0][0] = 0;
21    for(int i = 0; i < N; ++i){
22        for(int j = 0; j <= X; ++j){
23            for(int k = 0; k <= Y; ++k){
24                dp[i + 1][j][k] = min(dp[i][max(j - A[i], 0)][max(k - B[i], 0)] + 1, dp[i][j][k]);
25            }
26        }
27    }
28    cout << (dp[N][X][Y] == INF ? -1 : dp[N][X][Y]) << endl;
29}

補足情報（FW/ツールのバージョンなど）

DPは模範解答と同じく
DP[i + 1][j][k] = i番目までの弁当からj個のたこ焼きとk個のたいやきを揃えるための最小の弁当の数
と定義しました。

行動規範の内容に同意します

回答1件

ベストアンサー

ちょうどX個、Y個買う場合しか考慮されてないからです。
サンプルのケースだとちょうど5個と6個買うパターンがないので、解なしとなります。

投稿2021/10/01 00:57

yudedako67

総合スコア2047

rdld036

2021/10/01 10:26 編集

dp[i + 1][j][k] = min(dp[i][max(j - A[i], 0)][max(k - B[i], 0)] + 1, dp[i][j][k]); このようにすることで各dp[i][j][k]の値がピッタリだけでなく、j個以上、k個以上の場合も加味された値になり正しい答えが得られるということでしょうか。