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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。