#2023. 「Wdoi-2」灵山之上神风起

「Wdoi-2」灵山之上神风起

题目描述

简要题意

给定一个长度为 nn 的正整数序列 aa 满足对于所有 i∈[1,n]i\in [1,n] 有 ai∈{1,2,3}a_i \in \{1,2,3\}。

现在通过该序列构造一张含 nn 个节点,节点编号为 11 到 nn 的图:对于数 ii,如果 ai=1a_i=1,那么什么都不做;如果 ai=2a_i=2,那么向所有比 ii 小的数的节点连无向边;如果 ai=3a_i=3,那么向所有比 ii 大的数的节点连无向边。求出该图的最大独立集的大小。

最大独立集,指的是原图中一个点数尽量多的点集,这些点在原图中两两之间没有边直接相连。

原始题意

然而,东风谷早苗(后称早苗)的弹幕密度相当之高,使人应接不暇,灵梦只得想个方法去减少她需要关注的弹幕数量。

数个回合过后,她发现,早苗每次释放弹幕只会释放出 nn 个弹幕,分别编号为 1,2,…,n1,2,\dots,n,而她每释放一个弹幕,都会对应着产生一次神力波动。因而她的神力波动可以抽象为一个长度为 nn 的正整数数列 {an}\{a_n\}。由于她的资历尚浅,只会使用三种神力,分别用 1,2,31,2,3 表示,即 ∀i∈[1,n]\forall i \in [1,n],ai∈{1,2,3}a_i \in \{1,2,3\}。

她发现,早苗的三种神力作用各不相同,具体而言如下:

  • 当 ai=1a_i=1 时,她不会做任何事情。
  • 当 ai=2a_i=2 时,早苗会让第 ii 个弹幕向所有弹幕编号小于 ii 的弹幕建立神力输送通道。
  • 当 ai=3a_i=3 时,早苗会让第 ii 个弹幕向所有弹幕编号大于 ii 的弹幕建立神力输送通道。

接着,在各种神力的交互配合之下,密集的弹幕将展开于灵梦的眼前。而一旁的魔理沙发现,若是从这些弹幕中挑选出尽可能多的一群弹幕,使得每个弹幕之间不存在直接相连的神力输送通道,那么这群弹幕会产生【引发奇迹程度的能力】,是不必关注的。

由于【引发奇迹程度的能力】只能被触发一次,灵梦和魔理沙想要知道,最多有多少个弹幕是不必关注的。她们找到了你,希望你能帮她解答。

输入格式

  • 第一行,输入一个正整数 nn,表示弹幕总数。
  • 第二行,输入 nn 个正整数表示 aia_i,具体含义见题目描述。

输出格式

  • 共一行,输出一个正整数,表示最多有多少个弹幕是不必关注的。

    样例

6
3 1 3 2 1 2
2

题目来源:洛谷 P8538