2015 CCPC

• 求问长度为m的上升子序列的个数，m<=n<=1000.
• dp[i][j]表示包含第i个数的长度为j的上升子序列个数，那么显然是从前i-1个数
• 中小于等于a[i]的长度为j-1的状态求和转移过来，离散化后就用树状数组维护这个
• 转移就好了。

#include <map>
#include <cstdio>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 1007;
const int mo = 1e9+7;
int n, m;
int a[maxn], b[maxn];
long long bit[maxn][maxn];
void add(int j, int k, long long add)
{
    for(k; k <= n; k += -k & k){
        bit[j][k] = (bit[j][k] + add) % mo;
    }
}
long long sum(int j, int k){
    long long ret = 0ll;
    for(; k; k -= - k & k){
        ret = (ret + bit[j][k]) % mo;
    }
    return ret;
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int ti = 1; ti <= T; ti ++){
        std::map<int, int> map;
        memset(bit, 0, sizeof(bit));
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        int count = 0;
        std::sort(b+1, b+n+1);
        for(int i = 1; i <= n; i ++){
            if(b[i] > b[i - 1]) map[b[i]] = ++count;
            else map[b[i]] = count;
        }
        for(int i = 1; i <= n; i ++){
            add(1, map[a[i]], 1);
            for(int j = 2; j <= m; j ++){
                long long temp = sum(j - 1, map[a[i]] - 1) % mo;
                add(j, map[a[i]], temp);