HDU 5188 背包

本文主要是介绍HDU 5188 背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有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;
}

这篇关于HDU 5188 背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---