it's a dp difficult problem
试想如果我们遇见这样一道题，：
有n道题目，每道题有一个得分v和用时t；
我们要得够w分；用时最少 怎么做？？
这是一个裸奔的01背包
如果多一个规则，
每道题有一个开始时间，也就是开始做该题的时间不得少于一个时间st
现在怎么做？
我们应该把问题按照开始时间进行排序。
为什么？
用 st1 t1 与 st2 t2 来看
如果st1<st2
如果事情1先开始 那么所用时间ti1=st1+t1+（wait_time）t2
如果事情2先开始 那么所用时间是ti2=st2+t1+t2
从中可以看出ti1<ti2的
所以应该从开始时间少的开始做
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
#define cl(a,b) memset(a,b,sizeof(a)) ll dp[];
typedef struct data
{
int v,t,l;
}D;
D da[]; int cmp(D a,D b)
{
int ax=a.l-a.t,bx=b.l-b.t;
if(ax!=bx)return ax<bx;
return a.l<b.l;
} int main()
{
int n;
ll w;
while(scanf("%d %I64d",&n,&w)!=EOF)
{
cl(dp,);
int i,j,k,s=;
for(i=;i<n;i++)
{
scanf("%d %d %d",&da[i].t,&da[i].v,&da[i].l);
s+=max(da[i].t,da[i].l);
}
sort(da,da+n,cmp);
for(i=;i<n;i++)
{
int st=max(da[i].t,da[i].l);
for(j=s;j>=st;j--)
{
dp[j]=max(dp[j],dp[j-da[i].t]+da[i].v);
// cout<<i<<" * "<<j<<" * "<<dp[j]<<endl;
}
}
for(j=;j<=s;j++)
{
// cout<<j<<' '<<dp[j]<<endl;
if(dp[j]>=w)break;
}
if(j<=s)printf("%d\n",j);
else printf("zhx is naive!\n");
}
return ;
}