hdu 5188 zhx and contest [ 排序 + 背包 ]

传送门

zhx and contest

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 145    Accepted Submission(s): 49

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 are nhdu 5188 zhx and contest [ 排序 + 背包 ]

problems in the contest. He knows that he can solve the ihdu 5188 zhx and contest [ 排序 + 背包 ]thhdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

problem in thdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

units of time and he can get vhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

points.
As he is too powerful, the administrator is watching him. If he finishes the ihdu 5188 zhx and contest [ 排序 + 背包 ]thhdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

problem before time lhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

, he will be considered to cheat.
zhx doesn't really want to solve all these boring problems. He only wants to get no less than whdu 5188 zhx and contest [ 排序 + 背包 ]

points. 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 50hdu 5188 zhx and contest [ 排序 + 背包 ]

). Seek EOFhdu 5188 zhx and contest [ 排序 + 背包 ]

as the end of the file.
For each test, there are two integers nhdu 5188 zhx and contest [ 排序 + 背包 ]

and whdu 5188 zhx and contest [ 排序 + 背包 ]

separated by a space. (1≤n≤30hdu 5188 zhx and contest [ 排序 + 背包 ]

, 0≤w≤10hdu 5188 zhx and contest [ 排序 + 背包 ]9hdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

)
Then come n lines which contain three integers thdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ],vhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ],lhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

. (1≤thdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ],lhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]≤10hdu 5188 zhx and contest [ 排序 + 背包 ]5hdu 5188 zhx and contest [ 排序 + 背包 ],1≤vhdu 5188 zhx and contest [ 排序 + 背包 ]ihdu 5188 zhx and contest [ 排序 + 背包 ]≤10hdu 5188 zhx and contest [ 排序 + 背包 ]9hdu 5188 zhx and contest [ 排序 + 背包 ]hdu 5188 zhx and contest [ 排序 + 背包 ]

)

 
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 3
1 4 7
3 6
4 1 8
6 8 10
1 5 2
2 7
10 4 1
10 2 3
 
Sample Output
7
8
zhx is naive!
 
Source
 
Recommend
hujie   |   We have carefully selected several similar problems for you:  5189 5184 5181 5180 5177 

照例,先转一发官方题解:http://bestcoder.hdu.edu.cn/

1003 zhx and contest
状态压缩动态规划。i  表示当前已经做了的题的集合。f i   表示做完集合i中的所有题的最短用时。那么转移是相当简单的。但是也要注意判断状态是否合法时总分数可能会超过int范围。
另外有一种按l  排序后折半枚举的思路。但是这种思路是错的。因为很有可能做一道结束时间靠前的题会导致时间被卡,但是它又可以放到后面再做。就像背包不能贪心一样。 如官方发题解所说,不能按照l排序,这种贪心是错误的。
但是,可以按照 l-t 排序,即如果要选该题,那么浪费少的先选(如果不选,后面也不会选了),下面就是01背包了。 还是看不懂,为何n<=30也可以状压,不是应该妥妥 TLE+MLE的节奏吗? 难道是数据弱了? 等待大神博客ing
13130322 2015-03-15 10:11:17 Accepted 5188 202MS 14184K 1739 B G++ czy
 #include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <string> #define ll long long
int const N = ;
int const M = ;
int const inf = ;
ll const mod = ; using namespace std; int n,w;
int dp[N*M];
int sum;
int sumt,mal;
int ma; typedef struct
{
int t;
int v;
int l;
}PP; PP p[N]; bool cmp(PP a,PP b)
{
return a.l-a.t<b.l-b.t;
}
void ini()
{
int i;
sum=;sumt=;mal=;
for(i=;i<=n;i++){
scanf("%d%d%d",&p[i].t,&p[i].v,&p[i].l);
sum+=p[i].v;
sumt+=p[i].t;
mal=max(mal,p[i].l);
}
ma=mal+sumt;
sort(p+,p++n,cmp);
// for(i=1;i<=n;i++) printf(" i=%d t=%d v=%d l=%d\n",i,p[i].t,p[i].v,p[i].l);
} void solve()
{
if(sum<w) return;
memset(dp,,sizeof(dp));
int i,j;
for(i=;i<=n;i++){
//printf(" i=%d l=%d\n",i,p[i].l);
for(j=ma;j>=;j--){
if(j>=p[i].l){
if(j>=p[i].t)
dp[j]=max(dp[j],p[i].v+dp[ j-p[i].t ]);
}
else{
//dp[j]=dp[i-1][j];
}
//printf(" i=%d j=%d dp=%d\n",i,j,dp[j]);
}
}
} void out()
{
if(sum<w){
printf("zhx is naive!\n");
}
else{
int i;
for(i=;;i++){
if(dp[i]>=w){
printf("%d\n",i);break;
}
}
}
} int main()
{
//freopen("data.in","r",stdin);
//scanf("%d",&T);
//for(cnt=1;cnt<=T;cnt++)
while(scanf("%d%d",&n,&w)!=EOF)
{
ini();
solve();
out();
}
}
上一篇:hdu 5186(模拟)


下一篇:hdu 3966 Aragorn's Story(树链剖分+树状数组)