HDU - 2227 Find the nondecreasing subsequences

题意：求不递减的子序列的个数

思路：跟昨天那题HDU-3030不同的是，昨天的是严格的递增的子序列数，稍微修改一下就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int MOD = 1000000007;
const int MAXN = 100010;

ll arr[MAXN],n;
int num[MAXN],sortNum[MAXN];

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

void update(int x,ll d){
	while (x <= n){
		arr[x] += d;
		arr[x] %= MOD;
		x += lowbit(x);
	}
}

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

int main(){
	while (scanf("%lld",&n) != EOF){
		memset(arr,0,sizeof(arr));
		for (int i = 1; i <= n; i++){
			scanf("%d",&num[i]);
			sortNum[i] = num[i];
		}
		sort(sortNum+1,sortNum+1+n);
		for (int i = 1; i <= n; i++){
			int index = lower_bound(sortNum+1,sortNum+1+n,num[i])-sortNum;
			ll temp = sum(index);
			update(index,temp+1);
		}
		cout << sum(n) << endl;
	}
	return 0;
}

HDU - 2227 Find the nondecreasing subsequences,布布扣,bubuko.com

HDU - 2227 Find the nondecreasing subsequences

原文：http://blog.csdn.net/u011345136/article/details/23604313