2014
01-04

# Find the nondecreasing subsequences

How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, …., sn} ? 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}.

The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, …., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.

The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, …., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.

3
1 2 3

7

#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1000000007;
const int maxn=100000;
struct node{
int num;
int id;
}a[maxn+10];
__int64 dp[maxn+10];
int num[maxn+10];
int cmp(node a,node b){
if(a.num!=b.num)
return a.num<b.num;
return a.id<b.id;
}
int lowbit(int x){
return x&-x;
}
void update(int x,__int64 d){
for(;x<=maxn;x+=lowbit(x)){
dp[x]+=d;
if(dp[x]>=mod) dp[x]-=mod;
}
}
__int64 sum(int x){
__int64 ans=0;
for(;x>0;x-=lowbit(x)){
ans+=dp[x];
if(ans>=mod)     ans-=mod;
}
return ans;
}
int main(){
int n,i;
__int64 ans;
while(scanf("%d",&n)!=EOF){
ans=0;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++){
scanf("%d",&a[i].num);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++){
__int64 s=sum(a[i].id)+1;
update(a[i].id,s);
ans+=s;
if(ans>=mod) ans-=mod;
}
printf("%I64d\n",ans);
}
return 0;
}

1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧