首页 > 代码库 > HDU 2227 Find the nondecreasing subsequences (DP+树状数组+离散化)
HDU 2227 Find the nondecreasing subsequences (DP+树状数组+离散化)
Find the nondecreasing subsequences
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1442 Accepted Submission(s): 516
Problem Description
How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.
Output
For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
Sample Input
3
1 2 3
Sample Output
7
题目分析
题目大意：给你一个串，求这个串中不递减的子串有多少个？初一看，完全想不到会是用树状数组，但是他就是这么神奇，不递减就想到逆序数，逆序数又想到了树状数组，居然是用他。他是求子串有多少个，又要用到DP，这里DP就是用树状数组慢慢推上去，最后是注意是求和会溢出，记得%1000000007。
1 #include<iostream> 2 #include<stdio.h> 3 #include<memory.h> 4 #include<algorithm> 5 6 using namespace std ; 7 8 struct node 9 {10 int val, id ;11 }a[100005];12 13 bool cmp(node a, node b)14 {15 return a.val < b.val ;16 }17 18 int b[100005] , c[100005] , s[100005] ,n ;19 20 int lowbit( int i)21 {22 return i&(-i);23 }24 25 void update ( int i , int x )26 {27 while(i<=n)28 {29 s[i]+=x;30 if(s[i]>=1000000007)31 s[i]%=1000000007;32 i+=lowbit(i);33 }34 }35 36 int sum( int i )37 {38 int sum = 0 ;39 while( i > 0 )40 {41 sum += s[i] ;42 if( sum >= 1000000007)43 sum %= 1000000007;44 i-=lowbit( i ) ;45 }46 return sum ;47 }48 49 50 51 int main()52 {53 int i , res ;54 while(scanf("%d",&n)!=EOF)55 {56 memset( b , 0 , sizeof(b)) ;57 memset( s , 0 , sizeof(s)) ;58 for(i=1;i<=n;i++)59 {60 scanf("%d",&a[i].val);61 a[i].id = i ;62 }63 sort(a+1,a+n+1,cmp);64 b[a[1].id] = 1 ;65 for(i=2;i<=n;i++)66 {67 if(a[i].val!=a[i-1].val)68 b[a[i].id] = i ;69 else b[a[i].id] = b[a[i-1].id] ;70 }71 res = 0 ;72 for(i=1;i<=n;i++)73 {74 c[i] = sum( b[i] ) ;75 update ( b[i] , c[i]+1 ) ;76 }77 printf("%d\n",sum(n));78 }79 return 0 ;80 }