[Codeforces] 864E. Fire

題目連結:http://codeforces.com/problemset/problem/864/E

---

只感覺應該是DP，而且東東的順序會有影響，但是完全不知道該用何種順序來DP，看了tutorial才知道原來要按照消失時間來DP。
tutorial中其實並未給出證明，不過下面有人表示「如果你不先挑那些會先消失的人，那很有可能他待會就消失了(當然挑他要是有助益的)」，想了想我自己是覺得說，如果你可以先挑比較晚消失的人，再挑比較早消失的人，那你也一定可以先挑早消失再挑晚消失的，但反過來的挑法就不一定了。
那所以就按照那個順序排好序後，這題就變得類似於背包問題了，所以我們就可以跟背包一樣，用加入東東的方是想，每次加入一個物品就是在那些可行的範圍中往後加值之類的。

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
const int M = 2000 + 5;

struct Obj{
	int t, d, p;
	int id;
	inline bool operator<(const Obj &x) const {
		return d < x.d;
	}
} arr[N];
int sum[M];
vector<int> ori[M];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i].t>>arr[i].d>>arr[i].p;
		arr[i].id = i+1;
	}
	sort(arr, arr+n);
	for(int i=0;i<n;i++){
		for(int j=arr[i].d-1;j>=arr[i].t;j--){
			if(sum[j] < sum[j-arr[i].t]+arr[i].p){
				sum[j] = sum[j-arr[i].t]+arr[i].p;
				ori[j] = ori[j-arr[i].t];
				ori[j].push_back(i);
			}
		}
	}
	int mx = 0;
	for(int i=0;i<=2000;i++) if(sum[mx] < sum[i]){
		mx = i;
	}
	cout<<sum[mx]<<'\n';
	cout<<ori[mx].size()<<'\n';
	for(int i=0;i<(int)ori[mx].size();i++){
		cout<<arr[ori[mx][i]].id<<" \n"[i==(int)ori[mx].size()-1];
	}
	return 0;
}