AtCoder153E問題でWAになる理由が分かりません。

Question

AtCoder153E問題でWAになる理由が分かりません。提出コードは以下の通りです。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
const int INF = 1001001001;
ll mod = 1000000007;

int main()
{
	int h, n;
	cin >> h >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i];

	vector<vector<int>> mp(n, vector<int>(h + 1, INF));
	for (int i = 0; i < n; i++) mp[i][0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < h; j++) {
			int nj = min(j + a[i], h);
			if (0 < i) mp[i][nj] = min(mp[i][nj], mp[i - 1][nj]);
			if (mp[i][j] != INF) mp[i][nj] = min(mp[i][nj], mp[i][j] + b[i]);
		}
	}
	cout << mp[n - 1][h] << endl;
}

テストケースのmax_06がWAになります。入力例をデバッグで、ウォッチしましたが、自分なりに個数制限なしナップサックDPのアルゴリズムは組めていると思っています。現時点ではatcoder_testcasesにテストケースはアップされていません。上のコードのどこが間違っているのでしょうか？

Answer 1

            if (0 < i) mp[i][nj] = min(mp[i][nj], mp[i - 1][nj]);

この行の添え字が間違いでしょう。

10 2
1 1
9 3

例えばこんなテストケースの場合、明らかに答えは4ですが6が出力されます。
あとはデバッグすればわかると思います。

Comments

[sumachu]

テストケースありがとうございます。とても参考になりました。挙動は理解しました。コードはスマートではありませんが、以下のように変更したらACできました。

// i番目の魔法を使う場合を調査
if (0 < i) mp[i][j] = min(mp[i][j], mp[i - 1][j]); // i行目の情報を更新
if (mp[i][j] != INF) mp[i][nj] = min(mp[i][nj], mp[i][j] + b[i]);

// i番目の魔法を使わない場合を調査
if (0 < i) mp[i][nj] = min(mp[i][nj], mp[i - 1][nj]);