最长不下降子序列

题目大意:给定生成序列的方式,求这个序列最长不下降子序列.

我们定义的f[i]表示当lis长度为i的lis最小末尾是i,如果发现当前的a[i]比f[i]大,就直接压入,否则二分查找一个第一个比a[i]大的数字,覆盖掉,然后继续走

例子:

对于2 1 5 3 6 4 8 9 7这个序列

当我们搞完这些的时候,lis长度是5:{1,3,4,7,9}

注意,他只是存储对应长度lis的最小末尾,有了这个末尾我们就可以一个一个插入数据,虽然最后一个a[9]=7压入进去无贡献,假如后面再出现两个数组8和9,那么就可以把8更新掉9,9更新f[6]

lis最长长度为6

代码如下:

#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e6 + 66;

int n, t_0, A, B, C, D, len;
int res(1), a[N], b[N], f[N];

signed main()
{
    int i; n = read();

    t_0 = read(), A = read(), B = read(), C = read(), D = read();
    b[1] = a[1] = t_0;
    for (i = 2; i <= n; ++ i) b[i] = a[i] = (A * a[i - 1] * a[i - 1] + B * a[i - 1] + C) % D;

    sort(b + 1, b + 1 + n), unique(b + 1, b + 1 + n) - b - 1;
    for (i = 1; i <= n; ++ i) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;

    f[len = 1] = a[1];
    for (i = 2; i <= n; ++ i)
    {
        if (a[i] >= f[len]) res = max(res, len + 1), f[++ len] = a[i];
        else
        {
            int pos = upper_bound(f + 1, f + 1 + len, a[i]) - f;
            f[pos] = a[i];
            res = max(res, pos);
        }
    }

    put(res);
    return 0;
}

后记:

正解:因为是生成序列,所以有循环节,然后自己去找找憋一会就能憋出来.

上文中我说的是正统的nlogn的做法.

以前学过,最近忘了,忘得还不少...