JDOJ-1946: 求最长不下降序列的个数

Description

设有一个整数的序列：b₁,b₂,…，b_n，对于下标i₁<i₂<…＜i_m，若有b_i1≤b_i2≤…≤b_im
则称存在一个长度为m的不下降序列。（n < 10⁴）

现在有n个数，请你求出这n个数的最长不下降序列的长度及有多少个最长不下降序列

啊，我是最快的yeah！！！4ms

第一问，直接跑。将以每个数为结尾的最长不下降子序列的长度为下下标。我们发现这个下标的数组是递减的。所以我们二分，找到一个比当前元素小且下标最大的点。这个值得下标+1就是新的长度。然后用这个值来优化相同长度为下标的位置。这样就找到了最长不降子序列。然后呢？我们想，最长不下降的序列里的元素有什么特点：

1.每个元素的dp值就是位置。

2.每个元素只能通过原数列前面的比他小的元素且dp值刚好小1的dp状态转化过来。

所以，我们对于每一位，需要将前面dp值比他小1的元素的可能方案数累加，就是新的位置的方案数。然后，考虑，相同dp值的元素权值有一个特点就是肯定是递减的。（如果有一个元素的权大于前面的，那么他的dp值就可以是dp+1）。所以，我们维护一个链表，每次二分找到比他小的权值的点的左端点。维护一个前缀和，每次O(1)拿出来方案和。然后将新的点加到链表中。那么，维护最长的长度的前缀和就是答案。

没听懂就看代码。

对对对！！！还有一个就是，vector的下标是从零开始的。！！！v[i][0~size-1]，v[i].at(0~size()-1);

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,b[11000];
int dp[11000],f[11000],cnt,mx,tmp;
vector<int>v[20010];
int main()
{
    f[0]=-1<<30;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        if(b[i]>=f[cnt]) f[++cnt]=b[i],dp[i]=cnt;
        else
        {
            int l=1,r=cnt+1,mid;
            while(l<r)
            {
                mid=l+r>>1;
                if(f[mid]<=b[i]) l=mid+1;
                else r=mid;
            }
            f[l]=b[i]; dp[i]=l;
        }
    }
    v[0].push_back(-1<<30);
    v[0+n].push_back(1);
    for(int i=1;i<=n;i++)
    {
        int id=dp[i]-1;
        int l=0,r=v[id].size(),mid;
        while(l<r)
        {
            mid=l+r>>1;
            if(v[id][mid]<=b[i]) r=mid;
            else l=mid+1;
        }
        if(r==0) tmp=v[id+n][v[id+n].size()-1];
        else tmp=v[id+n][v[id+n].size()-1]-v[id+n][r-1];
        v[dp[i]].push_back(b[i]);
        if(v[dp[i]+n].size()) tmp+=v[dp[i]+n][v[dp[i]+n].size()-1];
        v[dp[i]+n].push_back(tmp);
    }
    printf("%d\n%d",cnt,v[cnt+n][v[cnt+n].size()-1]);
    return 0;
}

YEAH