Atcoder E

一看到题目就觉得是一个背包问题，但是不知道怎么写。

题解：直接求背包容量为2*h时所需要的花费。然后h~2h都是满足条件的，去最小值即可。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2E5+7;
const ll INF=1e9+7;
ll dp[N];
ll a[N],b[N];
int main(){
    ll h,c;
    cin>>h>>c;
    for(ll i=1;i<=c;i++) cin>>a[i]>>b[i];
    for(ll i=1;i<=2*h;i++) dp[i]=INF;
    for(ll i=1;i<=c;i++){
        for(ll j=1;j<=2*h;j++){
            dp[j]=min(dp[j],dp[max((ll)0,j-a[i])]+b[i]);
        }
    }
    ll ans=INF;
    for(ll i=h;i<=h*2;i++){
        ans=min(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}