AtCoder ABC #153 : E - Crested Ibis vs Monster

なんか妙に簡単だった回。
https://atcoder.jp/contests/abc153/tasks/abc153_e

問題

N種類の魔法を使い、敵の体力をH削り切りたい。
i番目の魔法では魔力をB[i]消費して体力をA[i]減らすことができる。
同じ魔法を何度も使えるとき、削りきる最小魔力はどの程度か。

解法

Hが小さいので単なる数の制限のないDP。

int H,N;
int A[10101],B[101010];
ll dp[20100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>N;
	FOR(i,20001) dp[i]=1LL<<60;
	dp[0]=0;
	FOR(i,N) {
		cin>>x>>y;
		FOR(j,H) dp[j+x]=min(dp[j+x],dp[j]+y);
	}
	
	ll mi=1LL<<60;
	for(i=H;i<=20000;i++) mi=min(mi,dp[i]);
	cout<<mi<<endl;
}

まとめ

400pt以下でもいいぐらいな気はするが。