Codeforces #214 Div2. C. Dima and Salad

夜うとうとしてしまい起きたら0:45だったので、参加はしませんでした。
今回は体感難易度C>D>Eだったけど、Cのパターンを知らなかっただけか。
http://codeforces.com/contest/366/problem/C

問題

N個の果物があり、それぞれのおいしさA[i]とカロリーB[i]が与えられる。
果物のうち幾つかを選択したとき、果物のおいしさの和がカロリーの和のちょうどK倍になるように選びたい。

そのような選び方のうち、おいしさの和の最大値を求めよ。

解法

おいしさとカロリーの総和はそれぞれ10000なので、おいしさとカロリーで２重ループを回すことはできない。
ここで、おいしさとカロリーの満たすべき条件は、(選んだA[i]の総和)/(選んだB[i]の総和)=K であるが、これは変形すると(選んだA[i]の総和) - K*(選んだB[i]の総和) = 0である。
よって、各果物において(A[i]-K*B[i])の値を足しながら最大おいしさをDPしていき、最終的にA[i]-K*B[i]の総和が0になるものを選べばよい。

K<=10なので、(A[i]-K*B[i])の和は-100000～100000程度と負になる場合もあるので注意。

int N,K;
int A[100001],B[100001];
int dpdp[2][200001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	MINUS(dpdp);
	dpdp[0][100000]=0;
	dpdp[1][100000]=0;
	FOR(i,N) {
		FOR(x,200001) if(dpdp[0][x]>=0) 
			dpdp[1][x+A[i]-K*B[i]]=max(dpdp[1][x+A[i]-K*B[i]],dpdp[0][x]+A[i]);
		memmove(dpdp[0],dpdp[1],sizeof(dpdp)/2);
	}
	
	_P("%d\n",dpdp[0][100000]?dpdp[0][100000]:-1);
}

まとめ

A/B=Kを維持したいときは、A-K*B=0となるようDPすればいいのか。
これは勉強になった。