/ Vijos / 题库 /

抢救文件

抢救文件

描述

现在,OI界出现了一位来无影去无踪的怪盗,那就是基德!曾经他盗窃了著名的Paris Sunshine,各位大牛为之震惊!所以,在这之后,许多大牛都废寝忘食,研究对付基德的有效办法,在这期间,为了防止基德再次来盗窃,OI总司令就决定派出OIER,来保护OI总部。现在你担任OI防御大队大队长(很不错的职位哦^-^),需要在OI总部里安排尽可能多的OI特制陷阱!原来OI总部是完全分离的两部分(牛吧!)需要铺设特殊的管道才能到达OI总部。现在,OIER为了保卫总部,设计了许多许多的陷阱,让基德自投罗网(基德:我也不是吃干饭的啊!飞过海:麻烦您不要再来了!);
现在有1份超级无敌大大大大大大大大大的大牛提供的宝贵规划资料,需要让你来部署.(大牛:按老夫的意思办,只要怪盗敢来,我就让他去警察局待着=。=)。

你的任务就是编出一个计算机程序,来实现这次规划!

格式

输入格式

数据格式如下:
第一行两个由空格分隔的整数x,y, 10<=x<=6000000000000, 10<=y<=1000000000000000. x表示OI总部间隔带的长度而y表示宽.
第二行是一个整数N(1<=N<=500000),表示分布在间隔带的陷阱对数.
接下来的N行每行有两个空格分隔的正数C,D(0<C,D<=x),描述每一对陷阱沿着间隔带与西边境线的距离(基德:恐怖,连境线都出来了,OI总部啥时候那么大了额d=.=),C表示北边间隔带陷阱的距离而D表示南边陷阱的距离. 在间隔带的同一边,任何两个陷阱的位置都是不同的.(大牛:废话!);

输出格式

在互不干扰的情况下所能布置的最多陷阱数目.(大牛:我来!就是两条通道互不交叉!!!!)

样例1

样例输入1

10 4
2
1 2
2 1

样例输出1

1

限制

各个测试点1s

提示

大家要注意管道的构造哦!^_^!

来源

from 飞过海

信息

ID
1638
难度
6
分类
动态规划 | 动态规划 | LIS 点击显示
标签
(无)
递交数
752
已通过
226
通过率
30%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

飞过海第一次模拟赛&OI总部对抗赛