質問編集履歴
3
説明の追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -178,7 +178,7 @@
|
|
|
178
178
|
|
|
179
179
|
###試したこと(追記:10/1)
|
|
180
180
|
|
|
181
|
-
[この方のコード](https://atcoder.jp/contests/abc219/submissions/26225562)を参考にし、以下のような貰うDPを作成しました。するとACされたのですが、元のコードとやっていることが同じに見えるのですが、なぜ結果が異なるのでしょうか。その点も教えていただけると幸いです。
|
|
181
|
+
[この方のコード](https://atcoder.jp/contests/abc219/submissions/26225562)を参考にし、以下のような配列の再利用を使わず貰うDPを作成しました。するとACされたのですが、元のコードとやっていることが同じに見えるのですが、なぜ結果が異なるのでしょうか。その点も教えていただけると幸いです。
|
|
182
182
|
|
|
183
183
|
```C++
|
|
184
184
|
|
2
説明の追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -176,7 +176,71 @@
|
|
|
176
176
|
|
|
177
177
|
|
|
178
178
|
|
|
179
|
-
|
|
179
|
+
###試したこと(追記:10/1)
|
|
180
|
+
|
|
181
|
+
[この方のコード](https://atcoder.jp/contests/abc219/submissions/26225562)を参考にし、以下のような貰うDPを作成しました。するとACされたのですが、元のコードとやっていることが同じに見えるのですが、なぜ結果が異なるのでしょうか。その点も教えていただけると幸いです。
|
|
182
|
+
|
|
183
|
+
```C++
|
|
184
|
+
|
|
185
|
+
#include <bits/stdc++.h>
|
|
186
|
+
|
|
187
|
+
using namespace std;
|
|
188
|
+
|
|
189
|
+
typedef long long ll;
|
|
190
|
+
|
|
191
|
+
typedef long double ld;
|
|
192
|
+
|
|
193
|
+
|
|
194
|
+
|
|
195
|
+
const int INF = 1e9;
|
|
196
|
+
|
|
197
|
+
|
|
198
|
+
|
|
199
|
+
|
|
200
|
+
|
|
201
|
+
int N, X, Y;
|
|
202
|
+
|
|
203
|
+
vector<int> A, B;
|
|
204
|
+
|
|
205
|
+
vector<vector<vector<int>>> dp;
|
|
206
|
+
|
|
207
|
+
int main(){
|
|
208
|
+
|
|
209
|
+
ios::sync_with_stdio(false);
|
|
210
|
+
|
|
211
|
+
cin.tie(0);
|
|
212
|
+
|
|
213
|
+
cin >> N >> X >> Y;
|
|
214
|
+
|
|
215
|
+
A.resize(N);
|
|
216
|
+
|
|
217
|
+
B.resize(N);
|
|
218
|
+
|
|
219
|
+
for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
|
|
220
|
+
|
|
221
|
+
dp.assign(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, INF)));
|
|
222
|
+
|
|
223
|
+
dp[0][0][0] = 0;
|
|
224
|
+
|
|
225
|
+
for(int i = 0; i < N; ++i){
|
|
226
|
+
|
|
227
|
+
for(int j = 0; j <= X; ++j){
|
|
228
|
+
|
|
229
|
+
for(int k = 0; k <= Y; ++k){
|
|
230
|
+
|
|
231
|
+
dp[i + 1][j][k] = min(dp[i][max(j - A[i], 0)][max(k - B[i], 0)] + 1, dp[i][j][k]);
|
|
232
|
+
|
|
233
|
+
}
|
|
234
|
+
|
|
235
|
+
}
|
|
236
|
+
|
|
237
|
+
}
|
|
238
|
+
|
|
239
|
+
cout << (dp[N][X][Y] == INF ? -1 : dp[N][X][Y]) << endl;
|
|
240
|
+
|
|
241
|
+
}
|
|
242
|
+
|
|
243
|
+
```
|
|
180
244
|
|
|
181
245
|
### 補足情報（FW/ツールのバージョンなど）
|
|
182
246
|
|
1
説明の追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -4,7 +4,19 @@
|
|
|
4
4
|
|
|
5
5
|
### 発生している問題・エラーメッセージ
|
|
6
6
|
|
|
7
|
+
入力サンプル
|
|
7
8
|
|
|
9
|
+
3
|
|
10
|
+
|
|
11
|
+
5 6
|
|
12
|
+
|
|
13
|
+
2 1
|
|
14
|
+
|
|
15
|
+
3 4
|
|
16
|
+
|
|
17
|
+
2 3
|
|
18
|
+
|
|
19
|
+
を与えると、2と返すべきところと-1と返してしまう。
|
|
8
20
|
|
|
9
21
|
### 該当のソースコード
|
|
10
22
|
|