首页 > 其他 > 详细

【题解】 2月19日 厦门双十中学NOIP2014模拟D2 T2 采药人接水果

时间:2020-02-28 19:18:15      阅读:64      评论:0      收藏:0      [点我收藏+]

【问题描述】

采药人虽然 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\) 不相交子序列即可。

【题解】 2月19日 厦门双十中学NOIP2014模拟D2 T2 采药人接水果

原文:https://www.cnblogs.com/HSY-2019/p/12378318.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!