yukicoder : No.2390 Udon Coupon (Hard)

割とすんなりだった。
https://yukicoder.me/problems/no/2390

問題

N枚の札があり、以下の使い方ができる。

• 札をA1枚使って、B1円得する。
• 札をA2枚使って、B2円得する。
• 札をA3枚使って、B3円得する。

最適な札の使い方をすると、最大いくら得できるか。

解法

Aがいずれも2000以下である。
よって、3種類中2種類は2000回以下だけ使えばよい。
2000枚以上使う1種と、残り2種類の使用回数を総当たりしよう。

ll N,A[3],B[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,3) cin>>A[i]>>B[i];
	ll ret=0;
	FOR(i,3) {
		swap(A[0],A[1]);
		swap(A[2],A[1]);
		swap(B[0],B[1]);
		swap(B[2],B[1]);
		FOR(x,2020) FOR(y,2020) {
			ll a=x*A[0]+y*A[1];
			ll b=x*B[0]+y*B[1];
			if(a<=N) ret=max(ret,b+(N-a)/A[2]*B[2]);
		}
	}
	cout<<ret<<endl;
}

まとめ

★3でもいい気はする。