C. Subsequences

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/597/problem/C

Description

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Sample Input

5 2
1
2
3
5
4

Sample Output

7

HINT

题意

给你n个数，然后问你长度为k的上升子序列有多少个

题解：

dp[i][j]表示坐标为i，长度为j的上升子序列的个数

然后我们转移就用前面小于a[i]的dp[k][j-1]的和转移过来就好了

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define maxn 100105
long long dp[maxn][12];
void add(int x,int y,long long val)
{
    for(int i=x;i<maxn;i+=i&(-i))
        dp[i][y]+=val;
}
long long sum(int x,int y)
{
    long long ans = 0;
    for(int i=x;i>0;i-=i&(-i))
        ans+=dp[i][y];
    return ans;
}
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    add(1,0,1);
    for(int i=0;i<n;i++)
    {
        int x;scanf("%d",&x);x++;
        for(int j=k+1;j>0;j--)
        {
            long long temp = sum(x,j-1);
            add(x,j,temp);
        }
    }
    long long ans = sum(n+1,k+1);
    printf("%lld\n",ans);
}

Codeforces Testing Round #12 C. Subsequences 树状数组维护DP

原文：http://www.cnblogs.com/qscqesze/p/4960186.html