codeforces 597C （树状数组+DP）

题目链接：http://codeforces.com/contest/597/problem/C

思路：dp[i][j]表示长度为i，以j结尾的上升子序列，则有dp[i][j]= ∑dp[i-1][k]（1<=k<j），由于要求前缀和，可以用树状数组优化

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
typedef long long ll;
const int N=1e5+3;
ll dp[12][N];
using namespace std;
void update(int i,int pos,ll num,int n)
{
    while(pos <= n)
    {
        dp[i][pos] += num;
        pos += lowbit(pos);
    }
}
ll sum(int i,int pos)
{
    ll res=0;
    while(pos)
    {
        res += dp[i][pos];
        pos -= lowbit(pos);
    }
    return res;
}
int main()
{
    int n,k,x;
    scanf("%d %d",&n,&k);
    for(int i = 1 ;i <= n ;i++)
    {
        scanf("%d",&x);
        update(1,x,1,n);
        for(int j = 2 ;j <= k+1 ;j++)
            update(j,x,sum(j-1,x-1),n);
    }
    printf("%I64d
",sum(k+1,n));
    return 0;
}