题意：zhx在比赛的时候有n道题目，第i道题目有一个分值vi，需要ti时间做完，而且必须在li或li之后完成。问zhx在获得至少w分数的情况下需要的最少时间。
做法：类似于01背包的做法，第i题可以选择做或者不做。先对题目按照li-ti（即第i道题最早的开始时间）从小到大进行排序。然后遍历，在此过程中维护一个top值，top指的是完成前I题之后尽可能迟的时间值。对于第i道题，li-ti到top的值才有更新的可能，，其他值都不可能被更新，所以dp的递推过程也只会在这里进行。
在以下代码中，dp[i]代表在时间i结束后所能获得的最大分数值。状态转移很简单的，dp[j+vec[i].t]=max(dp[j+vec[i].t],dp[j]+vec[i].v);//vec是题目的数组名。
#include<iostream>#include<cstdio>#include<algorithm>#include<climits>using namespace std;const int maxn=31;struct pnt{int l,t,sta,v;bool operator<(const pnt& b) const{return sta<b.sta;}}vec[maxn];int dp[300005];int main(){int n,w;long long sum;while(scanf("%d%d",&n,&w)!=EOF){sum=0ll;for(int i=0;i<n;i++){scanf("%d%d%d",&vec[i].t,&vec[i].v,&vec[i].l);vec[i].sta=vec[i].l-vec[i].t;sum+=vec[i].v;}if(sum<w) {printf("zhx is naive!\n");continue;}sort(vec,vec+n);int top=0;dp[0]=0;for(int i=0;i<n;i++){int ll=max(0,vec[i].sta);int rr=max(vec[i].l,top+vec[i].t);for(int j=top+1;j<=rr;j++)dp[j]=dp[j-1];//先用上一道题的状态来更新（假如第i道题不做）for(int j=rr-vec[i].t;j>=ll;j–)//需要逆序进行，参照01背包的一维做法dp[j+vec[i].t]=max(dp[j+vec[i].t],dp[j]+vec[i].v);top=rr;}int ans=0;for(int i=0;i<=top;i++){if(dp[i]>=w){ans=i;break;}}printf("%d\n",ans);}}
我知道按攻略去旅行的人往往玩得过于按步就班，
