CF436 Div2 E - Fire

問題

家が燃えている!😨 🔥🏠🔥
家には品物がn個あり、i個目の品物は、運び出すのにはt[i]秒かかり、燃え始めてからd[i]秒後には完全に燃え尽きてしまい、価値はp[i]である
品物は1個ずつしか運べず、完全に燃え尽きた瞬間に品物の価値は無くなる
(t[i]>=d[i]の品物は絶対に無事に運び出せない)
運び出す品物の価値の総和を最大化し、最大のときの価値の総和と、運び出す物の番号一覧を運び出す順に出力せよ

解法

dの昇順にソートすればよくあるナップサック問題になる
dp[i]: 燃え始めてからi秒後までに運び出せる品物の価値の総和の最大値
とすれば価値の総和の方は簡単

運び出す物の番号一覧とその順序はvectorで管理する
e[i]: 燃え始めてからi秒後までに運び出せる品物の価値の総和が最大となるときの、運び出す物の番号一覧
とすると、dpの遷移は今j秒でi番目の品物を運び出すときはdp[j+t[i]] = dp[j]+p[i]となるわけだけど、この時ついでにe[j]をe[j+t[i]]にコピーしてからe[j+t[i]]にiを追加すればいい

int n, t[101], d[101], p[101], dp[2020];
pair<int,int> ds[101];
vector<int> e[2020];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> t[i] >> d[i] >> p[i];
		ds[i] = {d[i], i};
	}
	sort(ds, ds+n);
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	rep(I,n) {
		int i = ds[I].second;
		for (int j=d[i]-t[i]-1; j>=0; j--) if (dp[j+t[i]]<dp[j]+p[i]) {
			dp[j+t[i]] = dp[j] + p[i];
			e[j+t[i]] = e[j];
			e[j+t[i]].push_back(i);
		}
	}
	int id = max_element(dp,dp+2020) - dp;
	cout << dp[id] << endl << e[id].size() << endl;
	rep(i,e[id].size()) cout << e[id][i]+1 << " \n"[i==e[id].size()-1];
}