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]; }