Codeforces 480(#274 Div1) D. Parcels

Codeforces 動的計画法

問題

n個の箱があり、i番目の箱は
時刻in[i]に倉庫に入り、out[i]に倉庫から出る。
この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。
この荷物を倉庫に出し入れするとv[i]円もらえる。


倉庫には、同時に全体でSの重さの荷物しか入れられない。
また、荷物は直前に入れた荷物の真上にのみ置くことができ、最も上にある荷物のみを取り出すことができる。


利益を最大にするように、倉庫に出し入れする荷物を選択したときの利益を求めよ。

制約条件

n≦500
0≦in[i]＜out[i]＜2*n
w[i], s[i], S≦1000
v[i]≦10^6

方針

O(N^2S)かかってよいのでDPするだけだった…


荷物iを倉庫に入れることができるのは、

  • 区間[ in[i], out[i] ]に入っている他の荷物の重さの合計がs[i]以下
  • 倉庫に入れるほかのどの荷物jも、区間[ in[j], out[j]]が区間[ in[i], out[i] ]に重ならない（両端で接するのはＯＫ）


という条件を満たすとき。
各in[i], out[i]を平面上に書くと、括弧の対応がとれてるような状態がvalidである感じのイメージ。
なので、内側にある[ in[i], out[i] ]からDPしていく。


dp[i][w]を、i番目の荷物を使い、全体の重さがw以下であるような荷物の出し入れ方をするときの最大の利益とする。
dp[i][w]は、
in[i]≦in[j], out[j]≦in[i]であるようなjを、重ならないようにいくつか選んだとき、
この選び方をTとすれば、dp[i][w] = max_T{Σ[j∈T] dp[j][w - w[i] ]} + v[i]となる。


この最大のTを選ぶ部分は、もう一度DPをする。
dp[i][w]の状態数はO(NS)なので、ここでO(N)をかけてよいので、
全部ループをまわして、よくある区間カバーの最大を求めるDPをすればよい。

ソースコード

const int N = 502;
int n, lim, in[N], out[N], w[N], s[N], v[N];
int cmp[2 * N];

int dp[N][1001];
int dp2[2 * N], stamp[2 * N];

int main(){
	vector<pair<pi, int> > ordByL, ordByW;
	vi ls;
	
	cin >> n >> lim;
	rep(i, n){
		cin >> in[i] >> out[i] >> w[i] >> s[i] >> v[i];
		ordByL.pb(mp(pi(in[i], out[i]), i));
		ordByW.pb(mp(pi(out[i] - in[i], in[i]), i));
		ls.pb(in[i]); ls.pb(out[i]);
	}
	sort(all(ordByL)); sort(all(ordByW));
	ls.pb(0); ls.pb(1001);
	sort(all(ls)); ls.erase(unique(all(ls)), ls.end());
	
	ordByW.pb(mp(pi(0, 0), n)); ordByL.pb(mp(pi(0, 0), n));
	 in[n] = 0; out[n] = 1001; s[n] = lim; n++;
	
	rep(i, n){
		cmp[in[i]] = lower_bound(all(ls), in[i]) - ls.begin();
		cmp[out[i]] = lower_bound(all(ls), out[i]) - ls.begin();
	}
	int sid = 0;
	
	rep(ii, n) rep(ww, lim + 1){
		int i = ordByW[ii].second;
		int mx = 0, next = 0;
		
		if(ww) dp[i][ww] = max(dp[i][ww], dp[i][ww - 1]);
		if(ww > s[i] || ww + w[i] > lim) continue;
		sid++;
		
		int k = 0;
		rep(jj, n){
			int j = ordByL[jj].second, l = cmp[in[j]];
			for(; k <= l; k++){
				int t = stamp[k] == sid ? dp2[k] : 0;
				mx = max(mx, t);
			}
			
			if(i != j && in[i] <= in[j] && out[j] <= out[i]){
				int r = cmp[out[j]];
				int t = mx + dp[j][ww];
				if(stamp[r] < sid || dp2[r] < t){
					dp2[r] = t, stamp[r] = sid;
					next = max(next, t);
				}
			}
		}
		dp[i][ww + w[i]] = max(dp[i][ww + w[i]], next + v[i]);
	}
	cout << dp[n - 1][lim] << endl;
	return 0;
}