MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    

 

题目地址:

     http://acm.hdu.edu.cn/showproblem.php?pid=2227 

题目描述:

Find the nondecreasing subsequences

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 211    Accepted Submission(s): 80


Problem DescriptionHow 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}.
InputThe 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.
OutputFor each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
Sample Input3 1 2 3
Sample Output7

 题目分析: 

         整整一天的时间, 终于是把这个题A了  ,HDU 第一,  纪念下.....................

1

HUT-MiYu

375MS

1824K

2358B

G++

2010-08-27 09:44:32

 但也没有什么值得高兴的,  题目的思路是 小A 的,  0rz.......................  现在还是没有理解树状数组是怎么解这一题的,  它的思路是怎样的,

一点也没明白,   刚开始做的时候, 还以为 输入数据已经是按非递减排序了, 所以直接用 公式 2^n - 1, WA ...

.....  问过小A 才发现, 输入数据是 随机的.  这时就要像找上升子串一样, 找到它 所有的上升子串.  这里用到了 树状数组, 继续理解-ing......

 

先发代码 :

 

/*MiYu原创, 转帖请注明 : 转载自 ______________白白の屋http://www.cnblog.com/MiYuAuthor By : MiYuTest      : 1Program   : 2227 */
#include <iostream>#include <algorithm>using namespace std;#define lowbit(x) (x&(-x))int num[100005];int numcopy[100005];int hash[100005];int com[100005];int nCount = 1;void add ( int x,int k ){while ( x <= nCount ){com[x] += k;if ( com[x] >= 1000000007 ) com[x] %= 1000000007;x += lowbit(x); } }int sum ( int x ){int s = 0;while ( x > 0 ){s += com[x];if ( s >= 1000000007 ) s %= 1000000007;x -= lowbit(x);} return s %= 1000000007;}int cmp (const void *a, const void *b){return *((int*)a) - *((int*)b); }int sfind ( int x ){int *p = (int *)bsearch ( &x,hash+1,nCount+1,sizeof ( int ),cmp ); return p - hash;}int find(int num){int top=1,bottom=nCount,mid=(top+bottom)/2,ans=mid;while(num!=hash[ans]){if(hash[mid]<=num){top=(ans=mid)+1;}else{bottom=mid-1;}mid=(top+bottom)/2;}return ans;}
inline bool scan_d(int &num)  //整数输入{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}int main (){int N;while ( scan_d ( N ) ){for ( int i = 0; i != N; ++ i )scan_d ( num[i] ),numcopy[i] = num[i];sort ( num, num + N );memset ( com,0,sizeof (com) );nCount = 1;hash[1] = num[0];for ( int i = 1; i < N; ++ i ){if ( num[i] != num[i-1] )hash[++nCount] = num[i]; } for ( int i = 0; i < N; ++ i ){int pos = find ( numcopy[i] ); int res = sum ( pos ) + 1;add ( pos,res );}cout << sum ( nCount ) << endl;}return 0;}

 

 

 

 

转载于:https://www.cnblogs.com/MiYu/archive/2010/08/27/1809842.html

总结

以上是生活随笔为你收集整理的HDOJ 2227 HDU 2227 Find the nondecreasing subsequences ACM 2227 IN HDU的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。