题解：P5972 [PA2019] Desant

· · 题解

好像是我初二的时候提出的一个问题，当时 u 群有人说存在 O(n^23^{n/3}) 做法，昨天晚上突然会做了！

考虑从前往后 DP，暴力是记录 S 表示目前选择的数的集合，这样状态数仍然是 O(2^n) 级别。

但我们注意到，设 i 后面的数分别为 x_1,x_2,\cdots,x_k，我们只关心 [1,x_1),(x_1,x_2),\cdots,(x_k,n] 这些每一段中选了多少个数。于是状态数不会超过每段长度 +1 的乘积，由柯西不等式可以知道一定在段长相同时取到最值，直接看成连续的情况来分析，简单求导可以得到最值在 e^{n/e}，由于问题是离散的于是最值大约是 3^{n/3}。

于是直接 DP 就可以了。时间复杂度是 O(n^23^{n/3})，使用 map 或许会被卡常，手写哈希表可以稳过。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int N=41;
const int M=(1<<22);
const int P=47;
int a[N],n;

struct HashMap{

pair<int,ll>vals[M];
vector<int>havs;
vector<int>act[M];

int head[M],nxt[M],tot;
int size(){return tot;}
void clear(){
    for(int i=1;i<=tot;i++)nxt[i]=0,vector<int>().swap(act[i]);
    for(int i:havs)head[i]=0;
    vector<int>().swap(havs),tot=0;
}
void Ins(vector<int>&A,pair<int,ll>val){
    int res=0;
    for(int x:A)res=(((res*P)+x+1)&(M-1));

    int p=head[res];
    if(!p)p=++tot,act[p]=A,vals[p]=val,havs.emplace_back(res),head[res]=p;
    else{
        while(act[p]!=A&&p)p=nxt[p];
        if(!p)p=++tot,act[p]=A,vals[p]=val,nxt[p]=head[res],head[res]=p;
        else{
            if(vals[p].fi==val.fi)vals[p].se+=val.se;
            else if(vals[p].fi>val.fi)vals[p]=val;
        }
    }
}

};

HashMap f[2];

signed main(void){

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

    int cur=0;
    vector<int>NaganoharaYoimiya(n+1,0);
    f[0].Ins(NaganoharaYoimiya,mk(0,1ll));

    for(int i=1;i<=n;i++){
        vector<int>x;f[cur^1].clear();
        for(int j=i;j<=n;j++)x.emplace_back(a[j]);
        sort(x.begin(),x.end());int p=0;
        for(int j=0;j<x.size();j++)if(x[j]==a[i])p=j;

        for(int _=1;_<=f[cur].tot;_++){
            auto A=f[cur].vals[_];
            int w=A.fi;ll cc=A.se;
            int nw=0;for(int j=p+1;j<f[cur].act[_].size();j++)nw+=f[cur].act[_][j];
            auto to=f[cur].act[_];int cnt=to[p]+to[p+1];
            to.erase(to.begin()+p);
            to[p]=cnt,f[cur^1].Ins(to,mk(w,cc));
            to[p]=cnt+1,f[cur^1].Ins(to,mk(w+nw,cc));
        }

        cur^=1;
    }

    vector<pair<int,ll> >ans(n+1);
    for(int i=1;i<=f[cur].tot;i++){
        auto vec=f[cur].act[i];auto A=f[cur].vals[i];
        assert(vec.size()==1);
        int cnt=vec[0];
        ans[cnt]=A;
    }

    for(int i=1;i<=n;i++)cout<<ans[i].fi<<" "<<ans[i].se<<endl;

    return 0;
}