torus711 のアレ

主に競技プログラミングの問題について書きます．PC 以外だと数式が表示されないかもしれないです

Codeforces #214, C : Dima and Salad

Codeforces 動的計画法

問題文

http://codeforces.com/contest/366/problem/C

概要

N 種類の野菜があり、i 番の野菜は甘さが $a_i$ でカロリーが $b_i$ である。
この中からいくつかの野菜を選び、できるだけ甘いサラダを作りたい。
ただし、選んだ野菜の集合を S としたとき、 $\frac{ \sum_{ i \in S } a_i }{ \sum_{ i \in S } b_i } = k$ となるようにしたい。
最大の甘さを求めよ。
不可能な場合は -1 で示せ。

解法

まず、制約式を変形します。
　 $\frac{ \sum_{ i \in S } a_i }{ \sum_{ i \in S } b_i } = k$
　 $\sum_{ i \in S } a_i = k \sum_{ i \in S } b_i$
なので、a の和と、b の和の k 倍が等しくなるような選び方をした上で、a （または b ) を最大化すればよいことになります。
二つの値が等しい ⇔ 差が 0　であり、ある野菜を選んだときの差の変化はそのときの a, b の値によらず一定なので、差が等しい状態は同一視できます。
従って、次のような DP を考えることができます。

dp[ i 個考慮した ][ 差が j ] := a の和の最大値

dp[ i ][ j ] からの遷移は i 番 ( 0-indexed ) の野菜を使うか使わないかの二通りなので、

dp[ i + 1 ][ j ] を dp[ i ][ j ] で更新
dp[ i + 1 ][ j + as[ i ] - K * bs[ i ] ] を dp[ i ][ j ] + as[ i ] で更新

となります。
計算が終了したあとの dp[ N ][ 0 ] の値が答えです。
ただし、差は負にもなりうるので二つ目の次元には適当に下駄を履かせる必要があります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

const int INF = INT_MAX / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, K;
	cin >> n >> K;

	VI as( n ), bs( n );
	FOR( a, as )
	{
		cin >> a;
	}
	FOR( b, bs )
	{
		cin >> b;
	}

	VVI dp( n + 1, VI( n * 100 * 10 * 4, -INF ) );
	const int OFFSET = dp[0].size() / 2;
	dp[0][ OFFSET ] = 0;

	REP( i, 0, n )
	{
		REP( j, 0, dp[i].size() )
		{
			dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );
			
			const int nj = j + as[i] - K * bs[i];
			if ( 0 <= nj && nj < dp[i].size() )
			{
				dp[ i + 1 ][ nj ] = max( dp[ i + 1 ][ nj ], dp[i][j] + as[i] );
			}
		}
	}

	cout << ( dp[n][ OFFSET ] == 0 ? -1 : dp[n][ OFFSET ] ) << endl;

	return 0;
}