大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
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}.
3 1 2 3
7
一看n达到了1e5的级别。就知道得nlogn算法。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair<int,int>pil; const int INF = 0x3f3f3f3f; const int MOD=1e9+7; const int maxn=1e5+10; int a[maxn],n,b[maxn+100]; LL dp[maxn],c[maxn+100]; int lowbit(int x) { return x&(-x); } void update(int x,LL val) { while(x<maxn) { c[x]=(c[x]+val)%MOD; x+=lowbit(x); } } LL query(int x) { LL sum=0; while(x>0) { sum=(sum+c[x])%MOD; x-=lowbit(x); } return sum; } int main() { while(~scanf("%d",&n)) { int cnt=1; CLEAR(c,0); REPF(i,1,n) { scanf("%d",&a[i]); b[cnt++]=a[i]; } sort(b+1,b+cnt); cnt=unique(b+1,b+cnt)-(b+1); for(int i=1;i<=n;i++) dp[i]=1; LL ans=0; for(int i=1;i<=n;i++) { int x=lower_bound(b+1,b+1+cnt,a[i])-b; dp[i]=(dp[i]+query(x))%MOD; update(x,dp[i]); ans=(ans+dp[i])%MOD; } printf("%I64d\n",ans); } return 0; } /* */
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117125.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...