题解 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])$。$j$从小到大循环保证了$k<j$,查询$f[i-1][j-1]$的前缀和保证了$a[k]<a[j]$。

复杂度$O(NMlogN)$。

双倍经验:UVA12983

$CODE:$

#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;
}