如何求LIS或者LCS的个数

我们以LIS个数的求法为例子。

首先，我们都知道我们可以用BIT来实现O(nlogn)的求法，其个数的求法亦是如此。

我们在更新时多定义一维num，从而建立一个二元组{len, num}，表示此时长度为len的LIS的数量为num。

我们每次在更新时，每次都要进行如下操作（假设此时的二元组编号为x）：

我们要判断此时更新的二元组的长度是否比原先的长，如果是的，则我们直接将当前的二元组赋值给目前的二元组x；
否则，我们要考虑长度相等的情况。这个时候我们可以将当前二元组的num的值加到x中，从而实现数量更新（其实挺简单的）
再者，如果此时x的len已经大于当前的len，不管，毕竟已经不优于x了，不用过多费口舌。

Code：

CPP

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

extern inline char gc()
{
    static char RR[23456], *S = RR + 23333, *T = RR + 23333;
    if (S == T)
        fread(RR, 1, 23333, stdin), S = RR;
    return *S++;
}
inline int read()
{
    int p = 0, w = 1;
    char c = gc();
    while (c > '9' || c < '0')
    {
        if (c == '-')
            w = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9')
        p = p * 10 + c - '0', c = gc();
    return p * w;
}
#define mod 1000000007
#define ri register int
#define sid 50050
int n, cnp, H[sid], a[sid];
struct aha
{
    int len, num;
} t[sid], f[sid];
void upd(aha &x, aha y)
{
    if (x.len > y.len)
    {
        return;
    }
    if (x.len < y.len)
    {
        x = y;
    }
    else
    {
        x.num += y.num, x.num %= mod;
    }
}
aha qry(int x)
{
    aha ret = {0, 1};
    for (ri i = x; i; i -= i & (-i))
    {
        upd(ret, t[i]);
    }
    return ret;
}
aha add(int x, aha v)
{
    for (ri i = x; i <= cnp; i += i & (-i))
    {
        upd(t[i], v);
    }
}
int main()
{
    n = read();
    for (ri i = 1; i <= n; i++)
    {
        a[i] = H[i] = read();
    }
    sort(H + 1, H + n + 1);
    cnp = unique(H + 1, H + n + 1) - H - 1;
    for (ri i = 1; i <= n; i++)
    {
        a[i] = lower_bound(H + 1, H + cnp + 1, a[i]) - H;
    }
    for (ri i = 1; i <= n; i++)
    {
        f[i] = qry(a[i] - 1);
        f[i].len++;
        add(a[i], f[i]);
    }
    aha ans = {0, 0};
    for (ri i = 1; i <= n; i++)
    {
        upd(ans, f[i]);
    }
    printf("%d\n", ans.num);
    return 0;
}

如何求LIS或者LCS的个数

文章操作

Code：

相关推荐

评论

如何求LIS或者LCS的个数