设为首页 加入收藏

TOP

hdu2227---Find the nondecreasing subsequences(dp+树状数组)
2015-11-21 01:00:22 来源: 作者: 【大 中 小】 浏览:2次
Tags：hdu2227---Find the nondecreasing subsequences

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

Author
8600

Recommend
lcy | We have carefully selected several similar problems for you: 2642 2688 1541 3030 3015

dp[i] 表示以第i个元素结尾的不下降序列个数
dp[i]=∑i?1j=1 dp[j] +1
n达10万,所以用树状数组来优化

/*************************************************************************
    > File Name: hdu2227.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年06月02日 星期二 18时33分24秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; static const int N = 100010; static const int mod = 1000000007; LL tree[N]; int lowbit(int x) { return x & (-x); } void add(int n, int x, LL val) { for (int i = x; i <= n; i += lowbit(i)) { tree[i] += val; tree[i] %= mod; } } LL sum(int x) { LL ans = 0; for (int i = x; i; i -= lowbit(i)) { ans += tree[i]; ans %= mod; } return ans; } LL dp[N]; int Arr[N]; int xis[N]; int cnt; int search(int val) { int l = 1, r = cnt; int mid; while (l <= r) { mid = (l + r) >> 1; if (xis[mid] == val) { break; } if (xis[mid] > val) { r = mid - 1; } else { l = mid + 1; } } return mid; } int main() { int n; while (~scanf("%d", &n)) { cnt = 0; memset(tree, 0, sizeof(tree)); for (int i = 1; i <= n; ++i) { scanf("%d", &Arr[i]); xis[++cnt] = Arr[i]; } sort(xis + 1, xis + cnt + 1); cnt = unique(xis + 1, xis + cnt + 1) - xis - 1; memset(dp, 0, sizeof(dp)); LL ans = 0; for (int i = 1; i <= n; ++i) { int val = search(Arr[i]); LL Sum = sum(val); dp[i] = 1 + Sum; dp[i] %= mod; add(n, val, dp[i]); ans += dp[i]; ans %= mod; } printf("%lld\n", ans); } return 0; }
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 2899 Strange fuction (求导.. 下一篇：c++ static 类成员

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: