Найдите общее количество возрастающих подпоследовательностей длины k [дубликаты]

Предположим, у меня есть массив 1,2,2,10.

Возрастающие подпоследовательности длины 3 равны 1,2,4 и 1,3,4 (на основе индекса).

Итак, ответ 2. ССЫЛКА на проблему

Мне нужно лучшее решение с использованием дерева BIT, которое могло бы улучшить мое решение. Я пытался использовать BIT-дерево, но выдает ошибку превышения срока.

Вот Код реализации BIT.

Я также пробовал прямой подход

for (i = 1; i<n;i++) 
  dp[i, 1] = 1

for (i = 1; i<n;i++) 
  for (j = 0; j<i-1;j++) 
    if array[i] > array[j]
     for (p = 2; p<k;p++) 
        dp[i, p] += dp[j, p - 1]

Пожалуйста помогите


java algorithm fenwick-tree
person QWE    schedule 14.12.2014    source источник
comment
@AerofoilKite я пытался использовать BIT, но все равно получаю ошибку TLE   -  person QWE    schedule 14.12.2014

Ответы (1)


arrow_upward
1
arrow_downward

Надеюсь, это поможет..

int dp[51][100001];

void update(int bit[], int idx, int val){
for(int x = idx;x <= 100000;x += x & -x){
    bit[x] += val;
    if(bit[x] >= MOD) bit[x] -= MOD;
}
}

int query(int bit[], int idx){
int ret = 0;

    for(int x = idx;x > 0;x -= x & -x){
        ret += bit[x];
        if(ret >= MOD) ret -= MOD;
    }

return ret;
}

int main(){
    int N,K;

    scanf("%d %d",&N,&K);

int ans = 0;

    for(int i = 0,x;i < N;++i){
        scanf("%d",&x);

        for(int k = K;k > 1;--k)
            update(dp[k],x + 1,query(dp[k - 1],x));

        update(dp[1],x + 1,1);
    }

    printf("%d\n",query(dp[K],100000));

    return 0;
}

Explanation:

input: 1
For input 1:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   
0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 // update for X=2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

input: 1 2
For input 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 2 0 0 0 2 0 0 0 0 0 0 0  // update for X=3, length 1; got 2 increasing subsequence  with length 1
0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0  // update for X=3, length 2;  got 1 increasing subsequence  with length 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

input: 1 2 2
For input 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 2 3 0 0 0 3 0 0 0 0 0 0 0  // update for X=3, length 1; got 3 increasing subsequence  with length 1
0 0 0 2 2 0 0 0 2 0 0 0 0 0 0 0  // update for X=3, length 2; got 2 increasing subsequence  with length 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  // But you have no increasing subsequence with length 3

input 1 2 2 10
For input 10:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  
0 0 1 2 3 0 0 0 3 0 0 1 1 0 0 0  // update for X=11, length 1
0 0 0 2 2 0 0 0 2 0 0 3 3 0 0 0  // update for X=11, length 2
0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0  // update for X=11, length 3;  got 2 increasing subsequence  with length 3; tihs is calculate with help of length 2

Каждый раз вы берете значение.. подсчитайте, сколько возрастающих подпоследовательностей вы нашли и постепенно обновляете для длины 3,2,1

person Shahriar    schedule 14.12.2014
comment
у тебя правильный ответ!!!! пожалуйста, объясните, что вы сделали - person QWE; 14.12.2014
comment
Предположим, вам нужны возрастающие подпоследовательности с длиной 3. Возьмите каждое входное обновление DP[3] для следующего значения с тем, что у вас есть с длиной 2 с входом.. - person Shahriar; 14.12.2014
comment
пожалуйста, объясните вкратце о вашем алгоритме, обновите свой ответ с хорошим объяснением - person QWE; 14.12.2014
comment
Надеюсь теперь поймешь.. - person Shahriar; 14.12.2014
comment
Когда я беру 10 в качестве входных данных.. я проверяю, сколько подпоследовательностей у меня уже есть со значением меньше 10.. тогда я обновлю длину 3 с результатом длины 2. потому что добавление 10 с длиной 2 даст длину 3.. - person Shahriar; 14.12.2014