有N道题，要求得到最少W分
给出N道题的：每道题用时T，分数V，，应在且必须在L时刻提交才能得分
问得到W分所用的最少的时间
以L-T排序，然后做01背包即可
#include "stdio.h"#include "algorithm"#include "string.h"using namespace std;struct Mark{int t,v,l,x;}mark[40];int dp[300010];bool cmp(Mark a,Mark b){ if (a.x!=b.x) return a.x<b.x;return a.l<b.l;}int Max(int a,int b){if (a<b) return b;else return a;}int main(){int n,m,i,j,ans,up,sum,sum1;while (scanf("%d%d",&n,&m)!=EOF){sum=sum1=up=0;for (i=1;i<=n;i++){scanf("%d%d%d",&mark[i].t,&mark[i].v,&mark[i].l);sum+=mark[i].v;sum1+=mark[i].t;up=Max(up,mark[i].l);mark[i].x=mark[i].l-mark[i].t;}if (sum<m) {printf("zhx is naive!\n"); continue;}up=Max(up,sum1);sort(mark+1,mark+n+1,cmp);memset(dp,0,sizeof(dp));for (i=1;i<=n;i++)for (j=up;j>=mark[i].l ;j–)dp[j]=Max(dp[j],dp[j-mark[i].t]+mark[i].v);ans=up+1;for (i=0;i<=up;i++)if (dp[i]>=m) {ans=i;break;}if(ans==up+1) printf("zhx is naive!\n");else printf("%d\n",ans);}return 0;}
快乐要懂得分享，才能加倍的快乐
