#2023. 「Wdoi-2」灵山之上神风起
「Wdoi-2」灵山之上神风起
题目描述
简要题意
给定一个长度为 的正整数序列 满足对于所有 有 。
现在通过该序列构造一张含 个节点,节点编号为 到 的图:对于数 ,如果 ,那么什么都不做;如果 ,那么向所有比 小的数的节点连无向边;如果 ,那么向所有比 大的数的节点连无向边。求出该图的最大独立集的大小。
最大独立集,指的是原图中一个点数尽量多的点集,这些点在原图中两两之间没有边直接相连。
原始题意
然而,东风谷早苗(后称早苗)的弹幕密度相当之高,使人应接不暇,灵梦只得想个方法去减少她需要关注的弹幕数量。
数个回合过后,她发现,早苗每次释放弹幕只会释放出 个弹幕,分别编号为 ,而她每释放一个弹幕,都会对应着产生一次神力波动。因而她的神力波动可以抽象为一个长度为 的正整数数列 。由于她的资历尚浅,只会使用三种神力,分别用 表示,即 ,。
她发现,早苗的三种神力作用各不相同,具体而言如下:
- 当 时,她不会做任何事情。
- 当 时,早苗会让第 个弹幕向所有弹幕编号小于 的弹幕建立神力输送通道。
- 当 时,早苗会让第 个弹幕向所有弹幕编号大于 的弹幕建立神力输送通道。
接着,在各种神力的交互配合之下,密集的弹幕将展开于灵梦的眼前。而一旁的魔理沙发现,若是从这些弹幕中挑选出尽可能多的一群弹幕,使得每个弹幕之间不存在直接相连的神力输送通道,那么这群弹幕会产生【引发奇迹程度的能力】,是不必关注的。
由于【引发奇迹程度的能力】只能被触发一次,灵梦和魔理沙想要知道,最多有多少个弹幕是不必关注的。她们找到了你,希望你能帮她解答。
输入格式
- 第一行,输入一个正整数 ,表示弹幕总数。
- 第二行,输入 个正整数表示 ,具体含义见题目描述。
输出格式
- 共一行,输出一个正整数,表示最多有多少个弹幕是不必关注的。
样例
6
3 1 3 2 1 2
2
题目来源:洛谷 P8538