Educational DP Contest : X - Tower

今回X,Yに苦戦しました。
https://atcoder.jp/contests/dp/tasks/dp_x

問題

N個の箱があり、それぞれ重さW[i]、耐久力S[i]、価値V[i]とする。
これらの箱の一部を縦１列に任意の順番で積み上げることを考える。

この際、各箱の上に積み重なる重さの総和は、自身の耐久力以下でなければならないとする。
条件を満たす積み上げ型の価値の総和の最大値を求めよ。

解法

問題は積み上げの順番（正確には逆順なので上から下に差し込んでいく順番）である。
それさえ決まれば、上から順に重さの総和に対する価値の最大値をDPで求めていけばO(N*max(S))程度ですむ。

このように順番が気になる問題の定石として隣り合う２つを比べてどっちを先にすればいいか考えるというものがある。
上から順に箱を定めていき、ここまでの重さの総和がXであるとする。
ここに箱iとjを下に差し込むとき、片方だったら順番は関係ないので、両方差し込む場合にどっちを先に差し込むのが良いか考える。

• iが先の場合、X≧S[i]かつX+W[i]≧S[j]でなければならない
• jが先の場合、X≧S[j]かつX+W[j]≧S[i]でなければならない

それぞれ後者の式を合わせると、S[i]-W[j]とS[j]-W[i]を比べて小さい方を取るのがよいことになる。
よって両者移項してi,jを合わせるとW[i]+S[i]とW[j]+S[j]の小さい順に処理するのがよい。

int N;
int W[1010],S[1010],V[1010];
pair<int,int> P[1010];

ll from[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i]>>S[i]>>V[i];
		P[i]={W[i]+S[i],i};
	}
	sort(P,P+N);
	ll ma=0;
	FOR(i,N) {
		j=P[i].second;
		for(x=S[j];x>=0;x--) {
			ll v=from[x]+V[j];
			ma=max(ma,v);
			if(x+W[j]<=10000) from[x+W[j]]=max(from[x+W[j]],v);
		}
	}
	cout<<ma<<endl;
	
}

まとめ

本番最初適当にソート順を何通りか試してしまった。