Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

12/24
12:42
一般动规与递推

[bzoj 4282] 慎二的随机数列

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

间桐慎二是间桐家著名的废柴,有一天,他在学校随机了一组随机数列, 准备使用他那强大的人工智能求出其最长上升子序列,但是天有不测风云,人有旦夕祸福,柳洞一成路过时把间桐慎二的水杯打翻了……
现在给你一个长度为 n 的整数序列,其中有一些数已经模糊不清了,现在请你任意确定这些整数的值,使得最长上升子序列最长(为何最长呢?因为间桐慎二向来对自己的人品很有信心)。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数 n。
接下来 n 行,第 i 行若为“K x” ,则表示第 i 个数可以辨认且这个数为 x;
若为“N” ,则表示第i 个数已经辨认不清了。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

第一行一个整数,表示最长的最长上升子序列长度。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
K 1
N
K 2
K 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据,n ≤ 100000,|x| ≤ 10^9

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

首先可以看出一个最优解一定是包含所有N,如果不包含的话可以把没用到的N代替它后面的那个K

然后把所有的K减去它前面的N的个数做一遍LIS就可以了,因为首先这显然是满足条件的一个解,而且对于最优解的所有K做一遍这样的操作后也肯定是一个上升子序列,所以得到的答案加上N的个数就是最优解

 

 

 

[bzoj 4282] 慎二的随机数列