Codeforces #436 Div2 E. Fire

遅れて参加したこともあり、グダグダな結果に。
http://codeforces.com/contest/864/problem/E

問題

火事場からN個のアイテムを取り出したい。
各アイテムの取り出しに成功すると、価値P[i]を得られる。
各アイテムは取り出すのに時間がT[i]かかる。取り出し終わるまでにD[i]以上時間がかかると、そのアイテムの価値がなくなる。

各アイテムの取り出し作業は分割や並列化できないとき、最大どれだけの価値のアイテムを取り出せるか。
取り出し方の順番を答えよ。

解法

２つのアイテムのどちらを先に取り出した方が良いかを考える。
１つしか取り出さないなら順番は関係ないし、両方取り出すならD[i]が大きい方を後回しにする方が良い。
これて取り出し順が確定するので、あとはナップサック問題をDPで解いて順番を復元するだけ。

int N;
int T[101],D[101],P[101];

int dp[2020];
vector<int> from[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<int,int>> cand;
	
	cin>>N;
	FOR(i,N) cin>>T[i]>>D[i]>>P[i], D[i]--, cand.push_back({D[i],i});
	
	sort(ALL(cand));
	FOR(i,2020) dp[i]=-1<<30;
	dp[0]=0;
	FORR(c,cand) {
		int i=c.second;
		for(x=D[i]-T[i];x>=0;x--) if(dp[x+T[i]]<dp[x]+P[i]) {
			dp[x+T[i]]=dp[x]+P[i];
			from[x+T[i]]=from[x];
			from[x+T[i]].push_back(i+1);
		}
	}
	
	int ma=max_element(dp,dp+2020)-dp;
	_P("%d\n",dp[ma]);
	reverse(ALL(from[ma]));
	_P("%d\n",from[ma].size());
	FOR(i,from[ma].size()) _P("%d%c",from[ma][from[ma].size()-1-i],(i==from[ma].size()-1)?'\n':' ');
	
}

まとめ

変に考えすぎてグダった。