TopCoder SRM 478 Div 1 Medium KiwiJuice

問題概要

容量Cのボトルに、それぞれbottle[i]のジュースが入っている。
以下の操作を0回以上任意に行い、ジュースを売るときの、最大の利益を求めよ。
ただし、xリットルのジュースの入ったボトルはprice[x]で売れる。

操作:
好きな2本の相違なるボトルA,Bを選び、Aが満タンかBが空になるまでBのジュースをAに注ぐ。

C≦50,
ボトルの本数≦15を満たす。

解法

sigmarさんの解説（g:topcoder:id:jackpersel:20100804）がわかりやすかった。
ボトルをk本選んでお互いに注ぐ場合、1本の空でも満タンでもないボトルができ、残りは全て空か満タン。かつ、それは順番に拠らない。

↑なんか僕はこういう「順番に拠らない」とかを見つけるのが弱い。
250もそうだけどさー。

すると、
(ある最適解)=(その中のボトルの一部を混ぜる)+(残りの最適解)
という関係からビットDPができる。

ある集合の中から部分集合を作る方法はwriterさんのコードのが目から鱗だった。

ソースコード

writerさんのほぼそのまま。

class KiwiJuice {
	public:
	int theProfit(int C, vector <int> bottles, vector <int> prices)
	{
		int n=bottles.size(),mazeru[32768]={0};
		rep(i,1<<n)
		{
			int sum=0,btl=0;
			rep(j,n)if(i&1<<j)sum+=bottles[j],btl++;
			mazeru[i]=prices[C]*(sum/C)+prices[0]*(btl-sum/C-1)+prices[sum%C];
		}
		
		int dp[32768]={0};
		rep(i,1<<n)for(int j=i;j>0;j=(j-1)&i)dp[i]=max(dp[i],dp[i^j]+mazeru[j]);
		
		return dp[(1<<n)-1];
	}
};