<分区>
假设我有一个数组 1,2,2,10。
长度为 3 的递增子序列是 1,2,4 和 1,3,4(基于索引)。
所以，答案是2。Problem LINK
我想要一个使用 BIT 树的更好的解决方案，它可以改进我的解决方案。
我曾尝试使用 BIT 树，但出现超出时间限制的错误。
这是 BIT implementation Code .
我也尝试过直接方法
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]
请帮帮我
最佳答案
希望这会有所帮助..
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
关于java - 找出长度为 k 的递增子序列的总数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27467047/