zhx and contestTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 455Accepted Submission(s): 158
Problem Description
As one of the most powerful brushes in the world, zhx usually takes part in all kinds of contests.One day, zhx takes part in an contest. He found the contest very easy for him.There areproblems in the contest. He knows that he can solve theproblem inunits of time and he can getpoints.As he is too powerful, the administrator is watching him. If he finishes theproblem before time, he will be considered to cheat.zhx doesn’t really want to solve all these boring problems. He only wants to get no less thanpoints. You are supposed to tell him the minimal time he needs to spend while not being considered to cheat, or he is not able to get enough points.Note that zhx can solve only one problem at the same time. And if he starts, he would keep working on it until it is solved. And then he submits his code in no time.
Input
Multiply test cases(less than). Seekas the end of the file.For each test, there are two integersseparated by a space. ()Then come n lines which contain three integers. ()
Output
For each test case, output a single line indicating the answer. If zhx is able to get enough points, output the minimal time it takes. Otherwise, output a single line saying "zhx is naive!" (Do not output quotation marks).
Sample Input
1 31 4 73 64 1 86 8 101 5 22 710 4 110 2 3
Sample Output
78zhx is naive!
Source
/* ***********************************************Author:CKbossCreated Time :2015年03月19日 星期四 10时26分15秒File Name:HDOJ5188.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int maxn=200100;int n,w;int sumtime,sumv;int dp[maxn*30];struct PB{int t,v,l;}pb[50];bool cmp(PB a,PB b){return a.l-a.t<b.l-b.t;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&w)!=EOF){sumv=0;for(int i=0;i<n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);pb[i]=(PB){x,y,z};sumv+=y;}if(sumv<w){puts("zhx is naive!");continue;}sort(pb,pb+n,cmp);memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)for(int j=maxn;j>=max(pb[i].t,pb[i].l);j–)dp[j]=max(dp[j],dp[j-pb[i].t]+pb[i].v);int ans=0;for(int i=0;i<maxn;i++)if(dp[i]>=w) { ans=i; break; }printf("%d\n",ans);}return 0;}
，即使是不成熟的尝试，也胜于胎死腹中的策略。
