数据结构优化DP

例题A题解

设 \(f_{i,j}\) 表示以第 \(i\) 位为结尾，长度为 \(j\) 的严格单调上升子序列的数量。
那么显然有 \(f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\times(a_k<a_i)\)
然后发现这玩应 \(O(n^2m)\) 直接寄掉了。
考虑优化。
发现只有当 \(a_k<a_i\) 时才会有贡献。
于是离散化+权值BIT就完事了。

例题A代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f=  -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10, mod = 123456789;
int n, a[maxn], m;
vector<int> vec;
struct BIT{
    int c[maxn];
    inline int lowbit(int x){return x & (-x);}
    void upd(int x,int upd){for(;x <= n;x += lowbit(x))c[x] = (c[x] + upd) % mod;}
    int qry(int x){int ans = 0;for(;x;x -= lowbit(x))ans = (ans + c[x]) % mod;return ans;}
    void clear(){for(int i = 0;i <= n;i++)c[i] = 0;}
}tree[101];
signed main(){
    while(scanf("%lld%lld",&n,&m) != EOF){
        for(int i = 1;i <= n;i++){vec.push_back(a[i] = read());}
        sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());
        int ans = 0;
        for(int i = 1;i <= n;i++){
            int x = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1;
            tree[1].upd(x,1);
            for(int j = 1;j <= m;j++)
                tree[j].upd(x,tree[j - 1].qry(x - 1));
        }
        ans = tree[m].qry(n);
        printf("%lld\n",ans);
        for(int i = 1;i <= m;i++)tree[i].clear();vec.clear();
    }
    return 0;
}