Description

間桐慎二是間桐家著名的廢柴，有一天，他在學(xué)校隨機了一組隨機數(shù)列，準(zhǔn)備使用他那強大的人工智能求出其最長上升子序列，但是天有不測風(fēng)云，人有旦夕禍福，柳洞一成路過時把間桐慎二的水杯打翻了……

現(xiàn)在給你一個長度為n 的整數(shù)序列，其中有一些數(shù)已經(jīng)模糊不清了，現(xiàn)在請你任意確定這些整數(shù)的值，使得最長上升子序列最長（為何最長呢？因為間桐慎二向來對自己的人品很有信心）。

Input

第一行一個正整數(shù)n。

接下來n 行，第i 行若為“K x”，則表示第i 個數(shù)可以辨認且這個數(shù)為x；若為“N”，則表示第i 個數(shù)已經(jīng)辨認不清了。

Output

第一行一個整數(shù)，表示最長的最長上升子序列長度。

Sample Input

4

K 1

N

K 2

K 3

Sample Output

3

Data Constraint

對于10%的數(shù)據(jù)，n ≤ 1000，不存在“N”。

對于30%的數(shù)據(jù)，“N”的個數(shù)≤ 20，0 ≤ x ≤ 100000。

對于100%的數(shù)據(jù)，n ≤ 100000，|x| ≤ 10^9。

Solution

• 首先提出一個猜想：一定有一個最優(yōu)方案包含所有的N

• 證明如下：

• 當(dāng)有N在方案序列外時，可以使方案更優(yōu)，不成立；

• 當(dāng)有N在方案序列內(nèi)時，可以代替其中一個數(shù)，從而使這個方案包含這個N。

• 那么猜想成立。所以答案就相當(dāng)于把確定的數(shù)拿出來，每個數(shù)等于原數(shù)減去之前N的個數(shù)。

• 然后對此序列做一次最長上升子序列，再加上N的總個數(shù)即可！

Code

#include<cstdio> #include<algorithm> using namespace std; int ans,sum; int f[100001]; inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') ch=getchar(),w=-1;while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } int main() {int n=read();f[0]=-1e9;for(int i=1;i<=n;i++){char ch=getchar();while(ch!='K' && ch!='N') ch=getchar();if(ch=='N') sum++; else{int x=read()-sum;if(f[ans]<x) f[++ans]=x; else f[lower_bound(f+1,f+1+ans,x)-f]=x;}}printf("%d",ans+sum);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 3693. 【NOI2014模拟6.20】慎二的随机数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。