CDOJ 1217 The Battle of Chibi【樹状配列+dp】

タイトルリンク:
http://acm.uestc.edu.cn/#/problem/show/1217
タイトル:
長さnのシーケンスを与え,長さmの厳密な上昇サブシーケンス個数を求める.
分析:
dp状態遷移方程式:列挙長と彼の前の彼より小さい元素は状態遷移を行い,時間複雑度O(n 3)である.樹状配列を用いて最適化すると,O(logn)は彼より前の小さい元素の長さiの上昇シーケンス個数を得ることができる.a[i]が大きいので,ここでは離散化を行う.

/* --I AM SUPER ROBBISH --Created by jiangyuzhu --2016/5/19 */
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define pr(x) cout << #x << ": " << x << " "
#define pl(x) cout << #x << ": " << x << endl;
#define sa(x) scanf("%d",&(x))
#define sal(x) scanf("%lld",&(x))
#define mdzz cout<<"mdzz"<<endl;
const int maxn = 1e3 + 5, maxm = 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
int bit[maxn][maxn];
int dp[maxn][maxn];
int nn;
int a[maxn], na[maxn];
int maxa;
void add(int i, int len, int x)
{
    while(i <= maxa){
        bit[i][len] = (x +  bit[i][len]) % mod;
        i += i & -i;
    }
}
int sum(int i, int len)
{
    int ans = 0;
    while(i){
        ans = (ans + bit[i][len]) % mod;
        i -= i &-i;
    }
    return ans % mod;
}
int main (void)
{
        int t;sa(t);
        int c = 1;
        while(t--){
            int n, m;sa(n);sa(m);
            for(int i = 0; i < n; i++){
                sa(a[i]);
                na[i] = a[i];
            }
            sort(na, na + n);
            nn = unique(na, na + n) - na;
            maxa = 0;
            for(int i = 0; i < n; i++){
                a[i] = lower_bound(na, na + nn,  a[i]) - na;
                a[i]++;
                maxa = max(maxa, a[i]);
            }
            memset(dp, 0, sizeof(dp));
            memset(bit, 0, sizeof(bit));

            for(int i = 0; i < n; i++){
                add(a[i], 1, 1);
                dp[i][1] = 1;
                for(int j = 2; j <= m; j++){
                    dp[i][j] = sum(a[i] - 1, j - 1);
                    add(a[i], j, dp[i][j]);
                    if(!dp[i][j]) break;
                }
            }
            printf("Case #%d: %d
", c++, sum(maxa, m));
        }
        return 0;
}
/* 100 5 2 1 1 1 2 2 9 3 1 1 1 2 2 2 3 3 3 3 2 1 2 3 3 2 3 2 1 */