0

配列 1,2,2,10 があるとします。

長さ 3 の増加するサブシーケンスは、1,2,4 および 1,3,4 (インデックス ベース) です。

というわけで、答えは 2 です。問題 LINK

ソリューションを改善できる 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]

私を助けてください

4

1 に答える 1

2

これが役立つことを願っています..

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 で徐々に更新します

于 2014-12-14T06:59:21.833 に答える