【JZOJ 3693】 慎二的随機數列

Description

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

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

對于100%的資料，n ≤ 100000，|x| ≤ 10^9。

Analysis

結論：存在最優解的一種方案，使得所有不确定的數都在最長上升子序列中

至于證明是顯然的

有了結論，可以把不确定的數拿掉，那麼再做DP的話要保證f[i]=f[j]+1時i到j中間的不确定的數的數量 < a[i]-a[j]

那麼這樣求出的LIS長度再把不确定的數加進來就是一種最優解

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=;
int n,m,ans,a[N],b[N];
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    char ch;
    scanf("%d\n",&n);
    int sum=;
    fo(i,,n)
    {
        scanf("%c",&ch);
        if(ch=='N') sum++;
        else scanf("%d",&a[++m]),a[m]-=sum;
        scanf("\n");
    }
    memset(b,,sizeof(b));
    fo(i,,m)
    {
        int pos=lower_bound(b+,b+m+,a[i])-b;
        b[pos]=min(b[pos],a[i]);
        ans=max(ans,pos);
    }
    printf("%d",ans+sum);
    return ;
}