题目大意：给定一个序列，求出其所有的上升子序列。
题解：一开始我以为是动态规划，后来发现离散后树状数组很好做，首先，c保存的是第i位上升子系列有几个，那么树状数组的sum就直接是现在的答案了，不过更新时不要忘记加1，因为当前元素本身也是一个子序列，比如数列离散后为1 3 2 4 5，那么第一位得到之前的答案为0，更新时1位加1,第二位算出为1，更新时3位加（1+1），第三位也一样，一次类推，同树状数组求逆序对的方法一样，但是更新的不是1，而是之前所有的答案数加1。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
#include <iostream> #include <cstdio> using
namespace std; const
int N=100005; const
int mod=1000000007; struct
node{int
id,v;}a[N]; int b[N],c[N],n; bool
cmp(node a,node b){return
a.v<b.v;}int sum(int
x){int
s=0;while(x>0)s+=c[x],s%=mod,x-=x&-x;return
s;} void
updata(int
x,int num){while(x<=n)c[x]+=num,c[x]%=mod,x+=x&-x;} int
main(){ while(scanf("%d",&n)!=EOF){ for(int
i=0;i<=n;i++)b[i]=c[i]=0; for(int
i=1;i<=n;i++){ scanf("%d",&a[i].v); a[i].id = i; } sort(a+1,a+n+1,cmp); b[a[1].id]=1; for(int
i=2;i<=n;i++){ if(a[i].v!=a[i-1].v)b[a[i].id]=i; else
b[a[i].id]=b[a[i-1].id]; } for(int
i=1;i<=n;i++)updata(b[i],sum(b[i])+1); printf("%d\n",sum(n)); } return
0; } |
HDU 2227 Find the nondecreasing subsequences,布布扣,bubuko.com
HDU 2227 Find the nondecreasing subsequences
原文：http://www.cnblogs.com/forever97/p/3577903.html