题目地址:HDU 5188 按照l-t排序,,l-t即最早开始的点。排完序后就是一个单纯的01背包了。 代码如下:
mod=1e9+7;;struct node{int t, l, v;}fei[40];LL dp[400000];bool cmp(node x, node y){return x.l-x.t<y.l-y.t;}int main(){int n, w, i, j, maxd, ans, maxl;while(scanf(“%d%d”,&n,&w)!=EOF){maxd=0,maxl=0;for(i=0;i<n;i++){scanf(“%d%d%d”,&fei[i].t,&fei[i].v,&fei[i].l);maxd+=fei[i].t;maxl=max(maxl,fei[i].l);}maxd+=maxl+1;sort(fei,fei+n,cmp);memset(dp,0,sizeof(dp));ans=INF;for(i=0;i<n;i++){for(j=maxd;j>=fei[i].l&&j>=fei[i].t;j–){dp[j]=max(dp[j],dp[j-fei[i].t]+(LL)fei[i].v);if(dp[j]>=(LL)w)ans=min(ans,j);}}if(ans==INF) puts(“zhx is naive!”);else printf(“%d\n”,ans);}return 0;}
一个人的旅行,反而会更贴近自己的内心,