首页 > ACM题库 > HDU-杭电 > hdu 2227 Find the nondecreasing subsequences-动态规划-[解题报告]C++
2014
01-04

hdu 2227 Find the nondecreasing subsequences-动态规划-[解题报告]C++

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

题意就不说了

有几个值得注意的地方,首先,数据范围太大,要离散化

有一个问题就是1 5 5

离散化后可能是1 3 2

本来应该是1 2 3的,就会出错

所以排序的时候加个按关键值排序,值相同时按id递增排序

#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;
}

解题转自:http://www.cnblogs.com/wuyiqi/archive/2012/01/12/2320918.html


  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小值吧