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
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.
). 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
)
1 4 7
3 6
4 1 8
6 8 10
1 5 2
2 7
10 4 1
10 2 3
8
zhx is naive!
照例,先转一发官方题解: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();
}
}
最新文章
- 使用C#代码生成一个随机的UUID
- 用c#开发微信 (12) 微统计 - 阅读分享统计系统 2 业务逻辑实现
- Virtualbox虚拟机安装Ubuntu图文版
- 2329: [HNOI2011]括号修复 - BZOJ
- sql sever怎样替换把表中数据。
- GWT(Google Web Tookit) Eclipse Plugin的zip下载地址(同时提供GWT Designer下载地址)
- poj2017简单题
- ANTLR3
- linux脚本: makefile以及链接库
- [2012-04-25]shell大括号参数扩展(Parameter Expansion)
- Row_Number() over()
- android开发环境配置以及测试所遇到的的问题
- Spring Cloud Gateway入门
- json数据格式 net.sf.json.JSONException: A JSONObject text must begin with &#39;{&#39; at character 1 of Error:(findColumns1)Read timed out
- Flexbox 布局的最简单表单 (转)
- C#存储过程中传入传出参数
- ubantu 与Windows 资源共享
- Android EditText 操作。。。
- BZOJ 2663: [Beijing wc2012]灵魂宝石
- BZOJ.1024.[SCOI2009]生日快乐(记忆化搜索)