【HDU4991】Ordered Subsequence(離散化+dp+樹狀數組)

記錄一個菜逼的成長。。

題目連結

題目大意:

給你n個數的序列，問長度為m的嚴格上升子序列有多少個。答案對123456789取模

(n≤10000,m≤100)

有一個暴力dp

dp[i][j] :=表示以第i個數結尾，上升子序列長度為j的個數

如果a[k] < a[i]

dp[i][j]+=dp[k][j−1]

複雜度 O(n2∗m) 顯然會T

這裡要用樹狀數組優化。

首先，先對序列n離散化，相同的數離散化後的值要一樣，這裡可以用map記錄。

其實就是對上升子序列長度為1~m的都建一顆樹

然後 dp[i][j] 就是 ∑dp[k][j−1] ，用樹狀數組來維護這個和

#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define clr clear()
#define cl(a,b) memset(a,b,sizeof(a))
typedef long long LL;
const int maxn =  + ;
const LL mod = ;
int a[maxn],b[maxn],n,m;
LL dp[maxn][],c[][maxn];
int lowbit(int x)
{
    return x&(-x);
}
void modify(int x,int y,int v)
{
    while(x < maxn){
        c[y][x] = (c[y][x] + v) % mod;
        x += lowbit(x);
    }
}
LL getSum(int x,int y)
{
    LL ans = ;
    while(x > ){
        ans = (ans + c[y][x]) % mod;
        x -= lowbit(x);
    }
    return ans;
}
map<int,int>ma;
int main()
{
    while(~scanf("%d%d",&n,&m)){
        cl(dp,);
        cl(c,);
        ma.clr;
        for( int i = ; i <= n; i++ ){
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(b+,b++n);
        for( int i = ; i <= n; i++ ){
            if(!ma[b[i]])ma[b[i]] = i;
        }
        LL ans = ;
        for( int i = ; i <= n; i++ ){
            //cout<<ma[a[i]]<<' ';
            dp[i][] = ;
            modify(ma[a[i]],,);
            for( int j = ; j < m; j++ ){
                dp[i][j+] = getSum(ma[a[i]]-,j);
                modify(ma[a[i]],j+,dp[i][j+]);
            }
        }

        for( int i = ; i <= n; i++ ){
            ans = (ans + dp[i][m]) % mod;
        }
        printf("%lld\n",ans);
    }
    return ;
}