寻找最优美做题曲线

查看题目戳这里

一道最长上升子序列的裸题

由题目描述可以看出，我们选择的日期中每天做题数量一定是递增的。这样，我们就能很轻易地想到用最长上升子序列去完成这道题。在这里，由于数据范围较大，我们需要用nlogn的算法去完成这道题。

那么，怎么去处理这必须做题的k天呢？

由于这k天做题数量一定是最长上升子序列的一部分，这样我们就可以发现有某些天是一定不能选的。当我们把这些一定不能选的日期删掉后就会发现，只要我们按照正常的算法去求最长上升子序列，那么这k天一定是包含在里面的。（想一想，为什么）
至于判断是否有最长上升子序列，只需要判读这必选的k天是否单调上升即可。
附一下代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
int n,k,cnt,t,a[500005],c[250005],sta[500005];
int mysort(int a,int b) {return a < b;}
int judge()
{
    sort(c + 1, c + k + 1, mysort);
    for(int i = 2; i <= k; i++)
        if(a[c[i]] <= a[c[i - 1]])
        {
            printf(“impossible”);
            return 1;
        }
    return 0;
}
void clean()
{
    for(int i = 1; i < c[1]; i++)
        if(a[i] >= a[c[1]])
            a[i] = -1;
    for(int i = 1; i < k; i++)
        for(int j = c[i] + 1; j <= c[i + 1] - 1; j++)
            if(a[j] <= a[c[i]] || a[j] >= a[c[i + 1]])
                a[j] = -1;
    for(int i = c[k] + 1; i <= n; i++)
        if(a[i] <= a[c[k]])
            a[i] = -1;
    for(int i = 1; i <= n; i++)
        if(a[i] != -1)
            a[++cnt] = a[i];
}
void two_fen(int k)
{
    int l = 1,r = t,mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(sta[mid] < k) l = mid + 1;
        else r = mid - 1;
    }
    sta[l] = k;
}
void work()
{
    sta[0] = -1008611;
    for(int i = 1; i <= cnt; i++)
    {
        if(a[i] > sta[t]) sta[++t] = a[i];
        else two_fen(a[i]);
    }
    printf(“%d\n”,t);
}
int main()
{
    scanf(“%d%d”,&n,&k);
    for(int i = 1; i <= k; i++) scanf(“%d”,&c[i]);
    for(int i = 1; i <= n; i++) scanf(“%d”,&a[i]);
    if(judge()) return 0;
    clean();
    work();
    return 0;
}