Atcoder解いてみた AtCoder Beginner Contest E - Crested Ibis vs Monster

AtCoder Beginner Contest E - Crested Ibis vs Monster

問題はこちら

回答

ナップザップDPを使う
加えて、モンスターの体力が0以下の状態を1つにまとめることもポイント

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N, H;
std::vector<int> A;
std::vector<int> B;

const long long inf = 1e18;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> H >> N;

	A.resize(N + 1);
	B.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		std::cin >> A[i] >> B[i];
	}

	// モンスターの体力がjの時のトキが使用した体力の最小値
	// モンスターの体力が0以下の状態はまとめてj=0で管理する
	std::vector<long long> dp = std::vector<long long>(H + 1, inf);
	
	// モンスターの体力がmaxの時は、トキも魔力を使っていない
	dp[H] = 0;
	for (int i = 1; i <= N; i++) {
		// i番目の魔法が最低1回は使用されることを想定
		// モンスターの体力が0以下でトキの勝ちなため、魔法が使われる条件はモンスターの体力が1以上の時
		for (int j = H; j >= 1; j--) {
			// i番目の魔法が選択される場合
			int remainlife = std::max(0, j - A[i]);
			long long selectval = dp[j] + B[i];
			dp[remainlife] = std::min(selectval, dp[remainlife]);
		}
	}


	// Nまでの魔法を見たかつ、モンスターの体力が0以下のdp値を出力
	std::cout << dp[0] << std::endl;

	return 0;
}