题意：失火了，有n个物品，每个物品有价值pi,必须在时间di前（小于di）被救，否则就要被烧毁。救某个物
品需要时间ti,问最多救回多少价值的物品，并输出救物品的顺序。
Examples
Input
3
3 7 4
2 6 5
3 7 6
Output
11
2
2 3
Input
2
5 6 1
3 3 5
Output
1
1
1
思路：有点像一个背包，dp数组记录的是当前时间所能获得的最大价值,转移方程dp[j]=max(dp[j],dp[j-t[i].ti]+t[i].w)
path[i][j]表示到i号物品j时间的状态时救的物品编号（这里是从0开始）
emmmmm 具体的在代码中加以注释。
代码：
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=2010;
struct node{
int ti,en,w,op;
}t[110];
int dp[maxn],path[110][maxn],a[110];
bool cmp(node x,node y){
if(x.en!=y.en)return x.en<y.en;
else return x.ti<y.ti;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>t[i].ti>>t[i].en>>t[i].w;
t[i].op=i+1;
//op为每个物品的标号，题目要求从1开始
}
memset(dp,0,sizeof(dp));
memset(path,-1,sizeof(path));//开始全部置为-1
sort(t,t+n,cmp);
int ma=0;
for(int i=0;i<n;i++){
ma=max(ma,t[i].en);
if(i!=0){
for(int j=0;j<t[i].ti;j++)path[i][j]=path[i-1][j];
//时间小于所需的营救时间，那么就不救，等于上一状态
}
for(int j=t[i].en-1;j>=t[i].ti;j--){
if(dp[j]<dp[j-t[i].ti]+t[i].w){
dp[j]=dp[j-t[i].ti]+t[i].w;
path[i][j]=i;
//如果救，那么就更新dp数组以及path数组为该物品
}
else if(i>0){
path[i][j]=path[i-1][j];
//如果不救，那么还是等于上一状态
}
}
}
int sum=0,temp=0;
for(int i=0;i<=ma;i++){
if(dp[i]>sum){
sum=dp[i];
temp=i;
//取出最大价值以及在最大价值的情况下，救完最后一个物品的时间
}
}
int k=n-1,c=0;
while(temp>0){
a[c++]=t[path[k][temp]].op;
temp-=t[path[k][temp]].ti;
k--;
k=path[k][temp];
//反着记录下路径
}
cout<<sum<<endl<<c<<endl;
for(int i=c-1;i>=0;i--){
if(i!=c-1)cout<<' ';
cout<<a[i];
//倒叙输出
}
cout<<endl;
return 0;
}