資料結構優化DP

考慮如下 DP 方程：
f ( x ) = min ? 1 ≤ i < x 且 h ( i ) < h ( x ) { f ( i ) + w ( i ) } f(x)=\min_{1\le i<x 且 h(i)<h(x)}\{f(i)+w(i)\} f(x)=1≤i<x且h(i)<h(x)min?{f(i)+w(i)}

考慮將 h h h 離散化，則能轉移給 f ( x ) f(x) f(x) 的 i i i 在 h 的離散序列中構成一段區間，可以用資料結構維護 h h h 的離散后的序列（通常需要支持插入、查詢），時間復雜度 O ( n log ? n ) O(n\log n) O(nlogn)，
單純地說太抽象了，還是來道例題看看吧，

例題：遞增子序列

題目大意

各處一行 n n n 個數字，問長度為 m m m 的嚴格上升子序列有多少個，

思路

dp[i][j] 為以第 i 個元素結尾，長為 j 的上升子序列的個數，則有：dp[i][j]=sum(dp[k][j-1]),a[k]<a[i] && k<i

可以看出這個方程相當于一個區間求和，優化以樹狀陣列為例：

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define _inf 0x3f3f3f3f
#define mod 123456789
#define ll long long
using namespace std;

int a[10010],b[10010],n,m;
ll c[105][10010];

int lowbit(int _)
{
    return _&(-_);
}

void upd(int _,int d,int k)
{
    while(_<=10000)
    {
        c[k][_]=(c[k][_]+d)%mod;
        _+=lowbit(_);
    }
}

ll get(int _,int k)
{
    ll ret=0;
    while(_)
    {
        ret=(ret+c[k][_])%mod;
        _-=lowbit(_);
    }
    return ret;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        int size=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+size+1,a[i])-b;//離散化
        ll _;
        for(int i=1;i<=n;i++)
        {
            upd(a[i],1,1);//初始化
            for(int j=1;j<m;j++)
            {
                _=get(a[i]-1,j);//區間和
                if(!_)break;
                upd(a[i],_,j+1);
            }
        }
        printf("%lld\n",get(10000,m)%mod);
    }
    return 0;
}