hdu-4991 Ordered Subsequence(dp+树状数组) Ordered Subsequence

hdu-4991 Ordered Subsequence(dp+树状数组)
Ordered Subsequence

题目链接：

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

A numeric sequence of a_i is ordered if a₁<a₂<……<a_N. Let the subsequence of the given numeric sequence (a₁, a₂,……, a_N) be any sequence (a_i1, a_i2,……, a_iK), where 1<=i₁<i₂ <……<i_K<=N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.

Your program, when given the numeric sequence, must find the number of its ordered subsequence with exact m numbers.

Input

Multi test cases. Each case contain two lines. The first line contains two integers n and m, n is the length of the sequence and m represent the size of the subsequence you need to find. The second line contains the elements of sequence - n integers in the range from 0 to 987654321 each.
Process to the end of file.
[Technical Specification]
1<=n<=10000
1<=m<=100

Output

For each case, output answer % 123456789.

Sample Input

3 2

1 1 2

7 3

1 7 3 5 9 4 8

Sample Output

题意：

求长为n的数组中的长度为m的单调递增子序列的个数;

思路：

跟又一次的CF一样,只不过这题还要离散化;

dp[i][j]表示以第j个结尾长为i的子序列的个数;

AC代码：

/*4991    655MS    9664K    1701 B    G++    2014300227*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
const ll mod=123456789;
int n,m;
ll sum[N],dp[102][N];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,ll num)
{
    while(x<=n)
    {
        sum[x]+=num;
        sum[x]%=mod;
        x+=lowbit(x);
    }
}
ll query(int x)
{
    ll s=0;
    while(x>0)
    {
        s+=sum[x];
        s%=mod;
        x-=lowbit(x);
    }
    return s;
}
struct node
{
    int num,pos,c,d;
};
node po[N];
int cmp1(node x,node y)
{
    if(x.num==y.num)return x.pos<y.pos;
    return x.num<y.num;
}
int cmp2(node x,node y)
{
    return x.pos<y.pos;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)scanf("%d",&po[i].num),po[i].pos=i;
        sort(po+1,po+n+1,cmp1);
        po[0].num=-1;
        for(int i=1;i<=n;i++)
        {
            if(po[i].num==po[i-1].num)
            {
                po[i].c=po[i-1].c;
            }
            else po[i].c=i;//po[i].c表示第一个跟po[i].num相同的数的位置;
            po[i].d=i;//表示po[i]插入时的位置;
        }
        sort(po+1,po+n+1,cmp2);
        for(int i=1;i<=n;i++)
        {
            dp[1][i]=1;
            update(po[i].d,1);
        }
        for(int i=2;i<=m;i++)
        {
            memset(sum,0,sizeof(sum));
            for(int j=1;j<=n;j++)
            {
                if(po[j].c>1)
                dp[i][j]=query(po[j].c-1);//转移方程;
                else dp[i][j]=0;
                update(po[j].d,dp[i-1][j]);//把dp[i-1][j]更新上去;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=dp[m][i];
            ans%=mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}

hdu-4991 Ordered Subsequence(dp+树状数组) Ordered Subsequence

相关推荐