codeforces-597C-Subsequences[트리 배열]

4274 단어 ACM_트리 배열codeforces
597C-Subsequences 
                time limit per test1 second memory limit per test256 megabytes

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.
input 5 2 1 2 3 5 4 output 7
제목 링크: cf-597C
제목 대의: 1~n에 n개의 수조가 있는데 이 n개의 숫자의 배열 순서를 제시하고 길이가 k+1인 최장 상승자 서열이 몇 개인지 물어본다.
제목 사고방식: 이 문제는 2015-CCPC의 문제와 유사하다.HDU-5542 문제 해결
다음은 코드입니다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define  lowbit(x)  ((x) & -(x))
ll num[100010];
ll dp[200010][12];
ll b[100010];
int n,m;
ll sum(ll x,ll y)   //  y      ， x         
{
    ll ret = 0;
    while(x > 0)
    {
        ret = (ret + dp[x][y]);
        x -= lowbit(x);
    }
    return ret;
}
void add(ll x,ll y,ll d)  //  x     ，    y   d
{
    while(x <= n)
    {
        dp[x][y] = (dp[x][y] + d);
        x += lowbit(x);
    }
}
int main(){
    while(scanf("%d%d",&n,&m) != EOF)
    {
        m += 1;
        memset(dp,0,sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld",&num[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= min(i+1,m); j++)
            {
                if (j == 1) add(num[i],1,1);
                else
                {
                    ll temp = sum(num[i] - 1,j - 1);
                    add(num[i],j,temp);
                }
            }
        }
        printf("%lld
",sum(n,m));
    }
    return 0;
}
단일 체인 테이블 의 전체 테이블 삭제
AWK &sed & 명령집 19 (MAC용)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage