题解 P1637 【三元上升子序列】

紫题 · 2019-03-23 21:03:09 · 题解

这道题可以拓展到M元上升子序列。

做法: DP + 树状数组优化

仿照LIS的做法，设f[i][j]为以a[j]为结尾的长度为i的上升子序列的个数。

得到状态转移方程：f[i][j] = {\sum_{k<j,a[k]<a[j]}}f[i-1][k]

转移时暴力枚举，显然复杂度为O(N^{2}M)

考虑到k有两个限制条件，k<j和a[k]<a[j]，可以先将a[]离散化，再用树状数组维护。

具体来说，在外层循环i，建立一个树状数组，以a[k]为下标存储f[i-1][k]的值。当内层循环到j时，f[i][j]+=ask(a[j]-1)，然后在转移到下一个j之前add(a[j],f[i-1][j])。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, a[30010], s[30010], m, f[4][30010], c[60010], ans;
ll val(int x) { return lower_bound(s+1, s+m+1, x) - s; }
ll ask(int x, ll sum = 0) {
    for(; x; x -= (x & (-x))) sum += c[x];
    return sum;
}
void add(int x, ll v) { for(; x <= m; x += (x & (-x))) c[x] += v; }
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i],  s[i] = a[i];
    sort(s+1, s+n+1);
    m = unique(s+1, s+n+1) - s - 1;
    for(int i = 1; i <= n; i++) f[1][i] = 1, a[i] = val(a[i]);
    for(int i = 2; i <= 3; i++) {
        memset(c, 0, sizeof(c));
        for(int j = 1; j <= n; j++) {
            f[i][j] = ask(a[j]-1);
            add(a[j], f[i-1][j]);
        }
    }
    for(int i = 1; i <= n; i++) ans += f[3][i];
    cout << ans << endl;
    return 0;
}