Zenn
🔥

ABC153 E - Crested Ibis vs Monster(C++)

2022/12/29に公開
AtCoder
tech

問題概要

問題文

体力Hのモンスターがいる。
N種類の魔法があり、 i番目の魔法を使うとモンスターの体力をA_i減らせる。しかし、これを使うにはコストB_iかかる。
モンスターの体力を0以下にするためには、最低でコストはいくら必要か求めてください。

制約

  • 1\leq H\leq10^4
  • 1\leq N\leq 10^3
  • 1\leq A_i\leq 10^4
  • 1\leq B_i\leq 10^4
  • 入力はすべて整数

問題リンク

メモ

いかにもdp

dp_i=体力をiにするために必要なコスト

とする。なお、iが負の時はdp_iをdp_0と同一視する。この時、
dp_{i-A_j}=\min(dp_{i-A_j},dp_i+b_j)

が成り立つ。より正確には、
dp_{\max(0,i-A_j)}=\min(dp_{\max(0,i-A_j)},dp_i+b_j)

である。そして、求めるものはdp_0である。
i=H,H-1,\dots,0と降順に求めることに注意!!!
状態数O(H),遷移にO(N)なので、計算量はO(NH)となり間に合う。

実装

#include<iostream>
#include<vector>
using namespace std;
int main(){
    const int INF=1e9;
    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<int> dp(h+1,INF);
    dp[h]=0;
    for(int i=h;i>=0;i--){
        for(int j=0;j<n;j++){
            int next_i=max(0,i-a[j]);
            dp[next_i]=min(dp[next_i],dp[i]+b[j]);
        }
    }
    cout<<dp[0]<<endl;
}

Discussion