bzoj1664 [Usaco2006 Open]County Fair Events 参加节日庆祝
Description
Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the N (1 <= N <= 10,000)
special events as he possibly can. He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!). Given a list of the events that FJ might wish to attend, with their start times
(1 <= T <= 100,000) and their durations (1 <= L <= 100,000), determine the maximum number of events that FJ can attend. FJ never leaves an event early.
有N个节日每个节日有个开始时间,及持续时间. 牛想尽可能多的参加节日,问最多可以参加多少. 注意牛的转移速度是极快的,不花时间.
Input
* Line 1: A single integer, N.
* Lines 2..N+1: Each line contains two space-separated integers, T and L, that describe an event that FJ might attend.
Output
* Line 1: A single integer that is the maximum number of events FJ can attend.
Sample Input
1 6
8 6
14 5
19 2
1 8
18 3
10 6
INPUT DETAILS:
Graphic picture of the schedule:
11111111112
12345678901234567890---------这个是时间轴.
--------------------
111111 2222223333344
55555555 777777 666
这个图中1代表第一个节日从1开始,持续6个时间,直到6.
Sample Output
OUTPUT DETAILS:
FJ can do no better than to attend events 1, 2, 3, and 4.
我会n^2的算法耶……幸好数据弱
首先把每个事件的开始时间、结束时间提出来快排,然后令f[i]表示快排后前i个最多能取多少个,枚举如果f[j].t<f[i].s,那么事件j一定在i前面,就可以用j来更新答案
其实注意到if (e[j].t<e[i].s) f[i]=max(f[i],f[j]+1)这一行,显然可以用平衡树加速,但是我很懒,又不会STL的set,就不打了
#include<cstdio>
#include<algorithm>
using namespace std;
struct event{
int s,t;
}e[10010];
int n;
int f[10010];
inline bool cmp(const event &a,const event &b)
{return a.s<b.s||a.s==b.s&&a.t<b.t;}
inline int max(int a,int b)
{return a>b?a:b;}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
e[i].s=read();
e[i].t=e[i].s+read()-1;
}
sort(e+1,e+n+1,cmp);
for(int i=1;i<=n;i++)
{
f[i]=1;
for (int j=1;j<i;j++)
if (e[j].t<e[i].s) f[i]=max(f[i],f[j]+1);
}
printf("%d",f[n]);
}
最新文章
- 使用s3cmd操作ceph rgw
- 【BZOJ-4515】游戏 李超线段树 + 树链剖分 + 半平面交
- 八、天气App案例
- CSS从大图片上截取小图标的操作以及三角形的画法
- cocos2d ARCH_OPTIMAL_PARTICLE_SYSTEM这个未定义的问题
- 使用python求字符串或文件的MD5
- PL/SQL语句块提高1+case语句
- HDU 4916 Count on the path
- [置顶] 如何使用c3p0+spring连接oracle数据库
- Python Data Visualization Cookbook 2.9.2
- dfs手写栈模板
- HTML5学习笔记<;一>;: 认识H5
- python API的安全认证
- 关于在arm裸板编程时使用printf问题的解决方法
- 【Teradata SQL】日历函数查询
- Python下用Scrapy和MongoDB构建爬虫系统(1)
- call,apply,bind
- Laravel validate 500异常 添加手机验证,中文验证与Validator验证的“半个”生命周期
- [svc]ssh+gg二步认证
- Bugtags 让你的 APP 测试轻松、上线安心