Buy Low, Buy Lower

给出一个长度为N序列\(\{a_i\}\)，询问最长的严格下降子序列，以及这样的序列的个数，\(1 <= N <= 5000\)。

解

显然我们可以很轻易地求出严格下降子序列，思维的过程应该是从熟悉走向不熟悉，从自然走向不自然，因此还是照搬老套路，设\(f_i\)表示以i结尾的最长严格下降子序列的长度，\(g_i\)表示这样的序列的方案数。

接着我们发现，方案之所以不能照搬转移，关键在于结尾有多个相同的数，它们的方案发生了叠加，再仔细研究，你会发现，最靠近i的数必然包括了所有的方案，于是我们只要桶排就可以做到寻找最近的数。

注意到数字可能很大，于是可以事先离散化，而且此题需要打高精度，然后就可以做了。

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define il inline

#define ri register

#define Size 5010

using namespace std;

struct lll{

    int num[75];

    il lll(){clear();}

    il void clear(){

        memset(num,0,sizeof(num));

        num[0]|=true;

    }

    il void read(){

        string s;cin>>s,num[0]=s.size();

        for(ri int i(1);i<=num[0];++i)

            num[i]=s[num[0]-i]-48;

    }

    il void print(){

        for(int i(num[0]);i;--i)

            putchar(num[i]+48);

        putchar('\n');

    }

    il bool operator!(){

        return num[0]==1&&num[1]==0;

    }

    il void operator=(string s){

        num[0]=s.size();

        for(ri int i(1);i<=num[0];++i)

            num[i]=s[num[0]-i]-48;

    }

    il lll operator+(lll x){

        lll y;y.clear();ri int i;

        for(i=1;i<=num[0]||i<=x.num[0];++i){

            y.num[i]+=num[i]+x.num[i];

            if(y.num[i]>9)y.num[i]-=10,++y.num[i+1];

        }if(i>1&&!y.num[i])--i;return y.num[0]=i,y;

    }

    il void operator+=(lll x){

        ri int i;

        for(i=1;i<=num[0]||i<=x.num[0];++i){

            num[i]+=x.num[i];if(num[i]>9)num[i]-=10,++num[i+1];

        }while(i>1&&!num[i])--i;num[0]=i;

    }

}fp[Size];

struct lsh{

    int a[Size],b[Size],n;

    il int look(int x){

        return b[x];

    }

    il void prepare(int x,int ar[]){

        n=x;

        for(ri int i(1);i<=n;++i)

            a[i]=ar[i];sort(a+1,a+n+1);

        for(ri int i(1);i<=n;++i)

            b[i]=dfs(ar[i]);

    }

    il int dfs(int x){

        int l(1),r(n),mid;

        while(l<=r){

            mid=l+r>>1;

            if(a[mid]<x)l=mid+1;

            else r=mid-1;

        }return l;

    }

}L;

bool b[Size];

int a[Size],dp[Size];

il void read(int&);

int main(){

    int n;read(n);

    for(int i(1);i<=n;++i)read(a[i]);

    L.prepare(n,a),a[++n]=-1;

    for(int i(1),j;i<=n;++i){

        memset(b,0,sizeof(b));

        for(j=i-1;j;--j)

            if(a[j]>a[i]){

                if(dp[j]>dp[i])

                    dp[i]=dp[j],fp[i]=fp[j],

                        b[L.look(j)]|=true;

                else if(dp[i]==dp[j]&&!b[L.look(j)])

                    fp[i]+=fp[j],b[L.look(j)]|=true;

            }

        ++dp[i];if(!fp[i])fp[i]="1";

    }printf("%d ",dp[n]-1),fp[n].print();

    return 0;

}

il void read(int &x){

    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

巴特西

Buy Low, Buy Lower

解

最新文章

热门文章