Codeforces #274 Div1 D. Parcels

このDPは思いつかん。
今回これ解いたけど、他のところでさらっと応用できるかな…。
http://codeforces.com/contest/480/problem/D

問題

初期状態で荷台の強度はSである。

ここにN個の荷物がやってくるので荷台の上にスタック状に積んでいく。
各荷物に対し到達時刻in[i]、発送時刻out[i]、重さw[i]、強度s[i]、価値v[i]が与えられる。

荷物が到達時刻に届くと、プレイヤーはそれを破棄しても良いし、スタックの最上位に積んでも良い。
ただし条件として

• 荷台の上に乗っかる荷物の総重量がSを超えてはならない
• 各荷物の上乗っかる荷物の総重量がs[i]を超えてはならない
• あとで発送時刻out[i]になったとき、上に別の荷物が乗っていてはならない。

同じ時刻に到着した荷物を載せる順番は任意である。
発送時刻out[i]が来ると、スタック最上位にその荷物があればそれを発行し、価値v[i]を得る。

最適に荷物を積むまたは破棄した場合、得られる総価値を答えよ。

解法

荷台と荷物を区別するのが面倒なので、荷台は価値0、強度S、到達時刻と発送時刻が全時間範囲に渡る荷物だとみなすと、区別が不要になる。

まず荷物を発送時刻の昇順にソートする。
次に、各荷物についてその荷物および他の荷物を上に積む場合の総重量ごとに価値を最大化するようDPする。

まずi番目の荷物に対し、総重量xを総当たりする。
その際、その荷物の上に詰めるのはmin(x-w[i],s[i])となる。
あとは0～out[i]の各時刻において、その上に積めうる価値の最大値を求める。
j番目の荷物を積む場合、0～in[j]までの間に詰める価値の最大値と、j番目以降の荷物を最大重量min(x-w[i],s[i])となる範囲で積んだ場合の和が上に積める最大値となる。

int N,S;
int V[1003];
int in[1003],out[1003],w[1003],s[1003],v[1003];
int dp[1003][1003];

int cmp(int a,int b) {
	if(out[a]<out[b]) return 1;
	if(out[a]>out[b]) return 0;
	return in[a]>in[b];
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N>>S;
	FOR(i,N) cin>>in[i]>>out[i]>>w[i]>>s[i]>>v[i];
	in[N]=0,out[N]=1000,s[N]=S;
	N++;
	FOR(i,N) V[i]=i;
	sort(V,V+N,cmp);
	FOR(i,N) {
		for(x=w[V[i]];x<=S;x++) {
			int dp2[1002];
			ZERO(dp2);
			int mw=min(x-w[V[i]],s[V[i]]);
			y=in[V[i]];
			FOR(j,i) if(in[V[j]]>=in[V[i]]) {
				for(;y<=in[V[j]];y++) dp2[y]=max(dp2[y],(y-1>=0)?dp2[y-1]:0);
				dp2[out[V[j]]]=max(dp2[out[V[j]]], dp[j][mw]+dp2[in[V[j]]]);
			}
			dp[i][x]=*max_element(dp2,dp2+out[V[i]]+1)+v[V[i]];
		}
	}
	cout << dp[N-1][S] << endl;
	
}

まとめ

このDPさらっと書ける気しないな…。