【题解】 2月19日 厦门双十中学NOIP2014模拟D2 T2 采药人接水果
【问题描述】
采药人虽然 AFO(SU)，但他在闲暇的时候还是可以玩一玩接水果(cat)的。但他渐渐发现 cat 好像有点太弱智。于是他不想浪费他的智商，于是决定写一个程序帮他玩。
cat 是这样玩的，开始时没有水果，采药人可以自己选择他所在的位置。接下来每隔 \(1\) 秒会有一个水果落到地上，而且第 \(i\) 秒落下的水果落到 \(x_i\) 这个位置，得分为 \(1\)。而采药人每秒只能移动一单位长度，但他不需要担心到了水果落下的位置还接不到水果，而且接水果不需要时间。采药人当然希望自己的分数越高越好。
采药人觉得写这个程序也太简单了，并且得分过低，于是他写了个挂，将接水果的一个人变成了两个人。但他却突然不想写 auto 程序了？这时转头看见了正在拼命切题的你，于是毫不犹豫地把这个问题交给了你。
【输入格式】
第 \(1\) 行：一个正整数 \(n\)，游戏时间有 \(n\) 秒
接下来 \(n\) 行：第 \(i+1\) 行，一个正整数 \(x_i\)
【输出格式】
共 \(1\) 行：最大得分
【数据范围】
对于 \(30\%\) 的数据，\(n\leqslant100\)
对于 \(60\%\) 的数据，\(n\leqslant1000\)
对于 \(80\%\) 的数据，\(n\leqslant10000\)
对于 \(100\%\) 的数据，\(n\leqslant500000\), \(x_i\leqslant50000\)
Solution
考虑用二元组 \((x,y)\) 来表示一个水果，其含义为 (出现时间, 出现位置)。
假设我们已经拿了第 \(a\) 个水果，接下来要去拿第 \(b\) 个水果，则需要满足的条件为：
\[
|b_y-a_y|\leqslant b_x-a_x
\]
\[
a_x-b_x\leqslant a_y-b_y\leqslant b_x-a_x
\]
\[
\begin{cases}
a_x+a_y\leqslant b_x+b_y\\
a_x-a_y\leqslant b_x-b_y
\end{cases}
\]
发现是个二维偏序的关系，由于有两个人接，求最长 \(2\) 不相交子序列即可。
最新文章
- Xcode 历史版本
- SSH Key连接github提示Permission denied (publickey).错误
- Bootstrap (导航、标签、面包屑导航)
- PAT (Basic Level) Practise：1012. 数字分类
- Failed to issue method call: Unit mysqld.service failed to load: No such file or directory.
- CDQ分治题目小结
- json包的loads dumps区分
- Integer和int的详细比较（转）
- SVG图像技术摘要
- Jfinal中Db类的的使用
- Spring和SpringMvc详细讲解
- elk kibana查询语法
- Linux文件系统2---VFS的四个主要对象
- WIN10安装和使用MySql5.6中遇到的一些问题与解决
- JAVA⑤
- Qt 菜鸟的坑 QAbstractSocket::isValid()
- asp.net网页中添加年月日时分秒星期。
- HTML 水平线
- Linux中Readlink命令
- fm 讲解加代码