立命館合宿2012 day3 問題E Elevator (AOJ 2366)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2366）

制約条件

n≦10000
1≦m≦n
W≦10000
ki≦15
Σki≦15
wi≦W

方針

全ての荷物を一階ずつ運んで、全て降ろすと考えてもエレベーターの移動量は同じ。

荷物の集合Sが決まったとき、それらを全て一つ下の階へ降ろすのに必要なエレベーターの往復回数をdp[S]とすれば、
dp[S]=min{dp[s]+1 | 集合S-sの荷物は一度にエレベータに載る}
という漸化式がたち、
計算量O(3^n)のDPが出来る。

ソースコード

int n,m,w;
int wi[15], nw;
int bit[10000],sum[1<<15];
int dp[1<<15];
int main(){
	cin>>n>>m>>w;
	rep(i,n){
		int k; cin>>k;
		rep(j,k){
			cin>>wi[nw];
			bit[i]|=1<<nw++;
		}
	}
	rep(i,1<<nw)rep(j,nw)if(i&1<<j)sum[i]+=wi[j];
	rep(i,1<<nw)dp[i]=inf;
	dp[0]=0;
	rep(i,1<<nw)for(int j=i;j;j=j-1&i){
		if(sum[j]<=w)dp[i]=min(dp[i],dp[i-j]+1);
	}
	int top=0;
	rep(i,n)if(bit[i])top=i;
	if(top==0){
		cout<<0<<endl; return 0;
	}
	int ans=abs(m-1-top), h=0;
	for(int i=top;i>0;i--){
		h+=bit[i];
		ans+=dp[h]*2-1;
	}
	cout<<ans<<endl;
	
	return 0;
	
}