HDU_2227 求不减子序列的个数（树状数组+DP）

83 阅读 0 评论 55 点赞

我是靠谱客的博主故意美女，最近开发中收集的这篇文章主要介绍HDU_2227 求不减子序列的个数（树状数组+DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目的意思比较明确，就是求不减子序列的个数。那道题目很容易想到的是dp来写，DP的地推公式就是

dp[i] = sum{dp[j] | j < i && a[j] <= a[i]}+1（dp[i]代表以I结尾的不减子序列的个数）注意每一个数只能用一次（原来一直把这道题想错的关键就是这里）

这个样子复杂度就是o(n^2)，肯定过不了，我们最多能接受的复杂度是o(n*log(n))，因为这又是一个区间和的问题，我们很容易想到用树状数组来写，由于s[i]太大，先进行离散化以后就可以做了，之前的dp转移方程能想到的话，那么树状数组也就随手写了。。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#define FOR(i,x,y)  for(int i = x;i < y;i ++)
#define rep(i,n)    for(int i = 0;i < n;i ++)
#define ll  long long
#define lrt rt<<1
#define rrt rt<<1|1
#define lson    rt<<1,l,mid
#define rson    rt<<1|1,mid+1,r
#define MAXN    111111
#define MOD     1000000007

using namespace std;

ll c[MAXN],s[MAXN],a[MAXN];
int n,m;

int lowbit(int x)   {return x&(-x);}

ll get_sum(int x){
    ll ans = 0;
    while(x){
        ans += c[x];
        ans %= MOD;
        x -= lowbit(x);
    }
    return ans;
}

void Modify(int x,int val){
    while(x <= n){
        c[x] += val;
        c[x] %= MOD;
        x += lowbit(x);
    }
}

int main(){
    while(~scanf("%d",&m)){
        map <ll,int> G;
        rep(i,m)    {scanf("%I64d",&s[i]);  a[i] = s[i];}
        sort(a,a+m);
        n = 0;
        G[a[0]] = (++n);
        FOR(i,1,m)  if(a[i] != a[i-1])  G[a[i]] = (++n);
        memset(c,0,sizeof(c));
        rep(i,m){
            int x = G[s[i]];
            int val = get_sum(x)+1;
            Modify(x,val);
        }
        printf("%I64dn",get_sum(n));
    }
    return 0;
}