HDU - 2227 Find the nondecreasing subsequences

本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---