题解：P5972 [PA 2019] Desant

· · 题解

给定一个 1 到 n 的排列 a_1,a_2,\cdots ,a_n，它有 2^n-1 个非空子序列。

请对于每个 k，找到一个长度为 k 的子序列，使得这个子序列的逆序对数量最少，并输出逆序对数量最少的子序列的数量。

考虑从前往后 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^2 3^{n/3})，使用 map 或许会被卡常, 手写哈希表可以稳过。

变进制状态存储（虽然我觉得你们都会）

考虑第一位 [0,a_1]，第二位在 [0,a_2]，...，第 k 位在 [0,a_k]​ 的向量如何存储。

记 p_i=\prod\limits_{j=1}^i (a_i+1)，然后考虑对向量 b_1,\cdots ,b_k，存储为 \sum\limits_{i=1}^k p_{i-1}b_i 即可，能空间 \prod(a_i+1)​ 精准存储，且不需要 map。

于是这题，对于每个 i，对 i 后面的 x_1, x_2, \cdots, x_k 使用变进制存储即可。转移的时候多算算状态。

类似题目：CF1552G，P10360

代码：

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,LL>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=45;
int n,a[N],c[N][N],ml[N][N],d[N],C[N],o[N];
vector<P>f,g;
inline void upd(P &x,P y){
    auto& [u,v]=x;auto [p,q]=y;
    if(p<u) x=y;else if(p==u) v+=q;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++) c[i][++d[i]]=a[j];
        sort(c[i]+1,c[i]+1+d[i]);c[i][++d[i]]=n+1;int s=1;
        for(int j=1;j<=d[i];j++) ml[i][j]=s,s*=c[i][j]-c[i][j-1];
        ml[i][d[i]+1]=s;
    }f={{0,1}};
    for(int i=1;i<=n;i++)
    {
        g=vector<P>(ml[i][d[i]+1],{999,0});
        int w=find(c[i-1],c[i-1]+n+1,a[i])-c[i-1];int S=0;
        for(auto [u,v]:f)
        {
            for(int j=d[i-1],x=S;j;j--) o[j]=x/ml[i-1][j],x%=ml[i-1][j];
            fill(C,C+d[i]+1,0);int ad=0;
            for(int j=1;j<=w;j++) C[j]=o[j];
            for(int j=w+1;j<=d[i-1];j++) C[j-1]+=o[j],ad+=o[j];
            auto calc=[&](){
                int s=0;
                for(int j=1;j<=d[i];j++) s+=ml[i][j]*C[j];
                return s;
            };
            upd(g[calc()],{u,v});C[w]++;
            upd(g[calc()],{u+ad,v});S++;
        }swap(f,g);
    }
    for(int i=1;i<=n;i++) cout<<f[i].first<<" "<<f[i].second<<"\n";
    return 0;
}