题目:http://acm.hdu.edu.cn/showproblem.php?pid=2227
题意:给定一个长度为n(n <= 100000)的整数序列,求其中的非降子序列的个数。
分析:如果n的值比较小,那么就是一个纯粹的dp题。设dp[i]表示以a[i]为结尾非降子序列的个数,其状态转移方程为:
可以看出,这样做的时间复杂度是,很显然不能这样做。
那么实际上,我们看到会想到逆序数,自然也会想到求逆序数最经典的做法就是树状数组,所以问题可以转化为求逆序数的对数,那么我们可以利用dp的思想递推下去,最终求得答案,可以看出这样做的时间复杂度为。
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; const int N = 100005; const int MOD = 1000000007; struct node { int id,val; }; int n; node a[N]; int aa[N],c[N],t[N]; bool cmp(node a,node b) { return a.val < b.val; } int Lowbit(int x) { return x & (-x); } void Update(int t,int val) { for(int i=t; i<=n; i+=Lowbit(i)) { c[i] += val; c[i] %= MOD; } } int getSum(int x) { int ans = 0; for(int i=x; i>0; i-=Lowbit(i)) { ans += c[i]; ans %= MOD; } return ans; } int main() { while(scanf("%d",&n)!=EOF) { memset(c,0,sizeof(c)); memset(aa,0,sizeof(aa)); for(int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].id = i; } sort(a+1,a+n+1,cmp); aa[a[1].id] = 1; for(int i=2;i<=n;i++) { if(a[i].val != a[i-1].val) aa[a[i].id] = i; else aa[a[i].id] = aa[a[i-1].id]; } for(int i=1;i<=n;i++) { t[i] = getSum(aa[i]); Update(aa[i],t[i]+1); } printf("%d\n",getSum(n)); } return 0; }