题目的意思比较明确,就是求不减子序列的个数。那道题目很容易想到的是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("%I64d ",get_sum(n)); } return 0; }