HDU 5188 zhx and contest(带限制条件的 01背包)
2024-08-27 22:53:15
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 n
problems in the contest. He knows that he can solve the
ith
problem in ti
units of time and he can get vi
points.
As he is too powerful, the administrator is watching him. If he finishes the
ith
problem before time li,
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
w
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.
One day, zhx takes part in an contest. He found the contest very easy for him.
There are n
problems in the contest. He knows that he can solve the
ith
problem in ti
units of time and he can get vi
points.
As he is too powerful, the administrator is watching him. If he finishes the
ith
problem before time li,
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
w
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
50).
Seek EOF
as the end of the file.
For each test, there are two integers n
and w
separated by a space. (1≤n≤30,
0≤w≤109)
Then come n lines which contain three integers ti,vi,li.
(1≤ti,li≤105,1≤vi≤109)
50).
Seek EOF
as the end of the file.
For each test, there are two integers n
and w
separated by a space. (1≤n≤30,
0≤w≤109)
Then come n lines which contain three integers ti,vi,li.
(1≤ti,li≤105,1≤vi≤109)
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!
题意:
- 有n道题i题用时ti秒,得分vi,在li时间点之前不能做出来,并且一道题不能分开几次做(一旦開始做,必须在ti时间内把它做完)
- 问得到w分的最小用时是多少
思路: 把题目按開始做的先后顺序排序,然后o1背包
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map> #define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1) #define eps 1e-8
typedef __int64 ll; #define fre(i,a,b) for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define ssf(n) scanf("%s", n)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f
#define N 100005 int dp[30*N]; struct stud{
int t,l,va;
bool operator < (const stud a) const
{
return l-t<a.l-a.t;
} }f[40]; int all,sum;
int n,m; void solve()
{
int i,j; sort(f,f+n); int te; mem(dp,0); fre(i,0,n)
free(te,all,f[i].l)
if(te>=f[i].t)
dp[te]=max(dp[te],dp[te-f[i].t]+f[i].va); fre(i,0,all)
if(dp[i]>=m) break; pf("%d\n",i);
} int main()
{
int i,j;
while(~sff(n,m))
{
sum=all=0;
int temp=0; fre(i,0,n)
{
sfff(f[i].t,f[i].va,f[i].l);
all+=f[i].t;
temp=max(temp,f[i].l);
sum+=f[i].va;
} if(sum<m)
{
pf("zhx is naive!\n");
continue;
} all=max(all,temp);
solve();
}
return 0;
}
最新文章
- Bootstrap table使用心得
- oracle数据库安装完要做的事情。
- IntelliJ IDEA - 代码辅助功能
- DSP下的#program
- zend studio 10.6 汉化破解
- JSTL标签出错:<;c:forEach var=";book"; items=";${requestScope.books}"; varStatus=";status";>;
- 【poj1716】 Integer Intervals
- 使用 Bumblebee 控制 NVIDIA 双显卡
- Django 1.10中文文档—第一个Django应用Part1
- split 函数自己实现
- 史上最全的AJAX
- abstract关键字
- mkdirs自动创建文件夹
- Python实现二分查找
- [TCP] 网络协议流程图
- css3实现小程序的动画
- MySQL:字符串字段加索引
- P2399 non hates math
- dns未设置 PHP Warning: file_get_contents():php_network_getaddresses: getaddrinfo failed:
- Mahout实现的算法