【BZOJ4282】慎二的隨機(jī)數(shù)列

Description

間桐慎二是間桐家著名的廢柴，有一天，他在學(xué)校隨機(jī)了一組隨機(jī)數(shù)列， 準(zhǔn)備使用他那強(qiáng)大的人工智能求出其最長(zhǎng)上升子序列，但是天有不測(cè)風(fēng)云，人有旦夕禍福，柳洞一成路過(guò)時(shí)把間桐慎二的水杯打翻了…… 現(xiàn)在給你一個(gè)長(zhǎng)度為 n 的整數(shù)序列，其中有一些數(shù)已經(jīng)模糊不清了，現(xiàn)在請(qǐng)你任意確定這些整數(shù)的值，使得最長(zhǎng)上升子序列最長(zhǎng)（為何最長(zhǎng)呢？因?yàn)殚g桐慎二向來(lái)對(duì)自己的人品很有信心） 。

Input

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

Output

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

Sample Input

4
K 1
N
K 2
K 3

Sample Output

3

HINT

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

題解：一開始想得極其復(fù)雜，看了Claris的題解后也覺(jué)得極不可做，然而直到看到了這個(gè)做法：

先統(tǒng)計(jì)有多少個(gè)N，然后將N去掉，然后對(duì)于每個(gè)k，我們令它的值-=它前面N的個(gè)數(shù)，最后跑最長(zhǎng)上升子序列即可。

不要問(wèn)我為什么是正確的。。。如果兩個(gè)K之間N的個(gè)數(shù)比這兩個(gè)數(shù)的差要多，那么為什么不直接將這個(gè)K扔掉呢。。。

?

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;
int n,m,sum;
int s[maxn];
char str[5];
inline int rd()
{int ret=0,f=1;	char gc=getchar();while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();return ret*f;
}
int main()
{n=rd();int i,v,l,r,mid;for(i=1;i<=n;i++){scanf("%s",str);if(str[0]=='K'){v=rd()-sum;l=1,r=m+1;while(l<r){mid=(l+r)>>1;if(s[mid]<v)	l=mid+1;else	r=mid;}if(l>m)	m++;s[l]=v;}else	sum++;}printf("%d",m+sum);return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/7898252.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ4282】慎二的随机数列 乱搞的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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