题意：
现在着火了，你要保留物品，每个物品有三个值t,d,p，t是解救需要的时间，d是过了多少秒这个物品就烧没了，p是物品价值，问保留物品最大的价值是多少，有多少个，分别是哪几个？
思路：
很明显的DP，而且总是觉得在哪里见过。dp[i]表示到时间为i为止，所能取得的最大价值，转移方程：dp[j]=max(dp[j],dp[j-a[i].t]+a[i].p)，有点类似于背包，只不过这里放的是时间。还有一点，如果把物品按照销毁时间进行排序，就不用担心时间出现冲突了，这样当前最优状态就可以由以前状态推导出来。这样就能求出最大价值。
然后，要求输出路径，path[i][j]表示对于按照时间顺序，取到第i个物品且时间是j时候的最优取法的情况，如果path[i][j]是i，则代表它是路径的末端（其实是第一个取走的），否则就是取得该情况的上一个的节点（-1代表不存在）。这样，我们首先遍历出最大价值，就能一步步找回路径了
（因为之前不会保存路径，也就在很多细节上想了许多，都写在注释里面了）
更新
上面的写法简直反人类，其实能够有更简单的写法，path[i][j]表示按照销毁时间顺序第i个物品，时间为j时是否能实现，这样我记录下最大时候的下标，就可以逆推了，这样的写法很好理解，也不容易错，就很优秀
我之前path[i][j]记录的是按照销毁时间顺序第i个物品，价值为j时是否能实现，emmmm，虽然能输出一个路径，但是很容易能想到会出现时间冲突。。。只能说
差之毫厘，谬以千里啊。。。
错误及反思：
一群 WA。主要是不会保存路径，只能现学，path的用法一开始想复杂了，导致出现了各种思路上的问题，最后还是找了个代码学习了一下才A的。。。
代码：
#include<bits/stdc++.h>
using namespace std;
struct poi{int num,t,d,p;operator < (const poi & x){return d<x.d;}
}a[110];
int dp[2100];
int ans[110];
int path[110][2100];
int n;
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d",&a[i].t,&a[i].d,&a[i].p);a[i].num=i+1;}sort(a,a+n);int maxn=0,times=0,tmp=0;memset(path,-1,sizeof(path));for(int i=0;i<n;i++){if(i){for(int j=1;j<a[i].t;j++)path[i][j]=path[i-1][j];}//在a[i].t之前的必定不会改变for(int j=a[i].d-1;j>=a[i].t;j--){if(dp[j-a[i].t]+a[i].p>dp[j]){dp[j]=dp[j-a[i].t]+a[i].p;path[i][j]=i;if(dp[j]>=maxn)//这里的等于号很关键，因为如果不是第一个出现的时间{ //那么在推导路径的时候，就会有可能重复选择maxn=dp[j];//比如：对于1物品来说，1-10分钟的最优选择都是1物品（也就是说1物品花费1分钟）tmp=j; //而如果对于2物品来说，如果1-10分钟的最优还是1物品} //那么我们在选择的时候，如果是以9分钟的条件返回的（就是说我们跳过了2物品）} //我们就还会再选择一次1物品else if(i)//没改变就继承下来path[i][j]=path[i-1][j];}//以外的区间没有对path操作是因为我们不可能选择该物品了，也就没有必要了}int tmp1=n-1;while(tmp>0){ans[times++]=a[path[tmp1][tmp]].num;tmp-=a[path[tmp1][tmp]].t;tmp1--;//向前找物品tmp1=path[tmp1][tmp];}printf("%d\n%d\n",maxn,times);for(int i=times-1;i>=0;i--)printf("%d ",ans[i]);puts("");
}
更新后更好理解的思路的代码:
#include<bits/stdc++.h>
using namespace std;
struct poi{int num,t,d,p;
}a[110];
int dp[2010];
int path[110][2010];
int ans[110];
int n;
bool cmp(poi x,poi y){return x.d<y.d;
}
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d",&a[i].t,&a[i].d,&a[i].p);a[i].num=i+1;}sort(a,a+n,cmp);int maxn=0;int times=0;for(int i=0;i<n;i++){for(int j=a[i].d-1;j>=a[i].t;j--){if(dp[j-a[i].t]+a[i].p>dp[j]){dp[j]=dp[j-a[i].t]+a[i].p;path[i][j]=1;if(dp[j]>dp[maxn])maxn=j;}}}printf("%d\n",dp[maxn]);int cnt=n-1;while(cnt>=0){if(path[cnt][maxn]==1){ans[times++]=a[cnt].num;maxn-=a[cnt].t;}cnt--;}printf("%d\n",times);for(int i=times-1;i>=0;i--)printf("%d ",ans[i]);puts("");}