[PA2019] Desant Solution

· · 题解

[PA2019] Desant Solution

推销。

原题链接。

题目大意：给定一个长为 n(n\le 40) 的排列，对于每个 i 求出长度为 i 的子序列逆序对最少有多少，并且求出有多少个长度为 i 的子序列逆序对最少。

解题思路：首先有一个暴力的做法，设 f_{i,S} 表示考虑完前 i 个数，选择了集合 S 的最少逆序对数、方案数。这样做至少是 O(n2^n)，非常不优美。我们发现我们只关心比当前位置大的数有多少个，所以我们把 S 中所有数都记录下来是有些多余的。考虑优化状态。

对于考虑完了前 i 个数，我们把 i 以后的数排序，记为 x_1,x_2,\cdots，我们只需要记录 [1,x_1),(x_2,x_3),\cdots,(x_{end},n] 这样每个区间内选了多少个数即可。于是我们可以设状态 f_{i,T_1,T_2,\cdots}，T_i 表示第 i 个区间内选了多少个数。

考虑计算状态的个数，我们就是求和为 n 的若干个数乘积最大是多少。严谨证明我不会，但是根据小学奥数，我们只要尽可能多拆 3，其次拆 2，尽量少拆成 1，这是因为如果我们考虑一个大于 3 的数，把它对半拆开乘积一定会更大，如 5<2\times 3。因此可以想到，最坏情况下，状态数是 O(3^{\frac n 3})，实际上这与严谨证明下的结论一致。因此状态数是可行的。

再回到状态上来，我们可以对于第 i 个长度为 len_i 的区间，用第 i 位上的 (len_i+1) 进制表示，即记 w_i=\prod_{j=1}^{i-1}(len_j+1)，设 cnt_i 为第 i 个区间选了多少个数，则 T=\sum_{i=1}^{end}cnt_iw_i，这样就能用整型表示状态 f_{i,T}，用 vector 连续开 \prod (len_i+1) 个位置即可，比哈希快多了。

而对于转移，每次决策选或不选都会合并两个区间。暴力地拆出状态的每一位和合并状态的每一位即可。

时间复杂度 O(n^23^\frac{n}3)，注意方案数要开 long long。

AC 代码：

int n;
const int N=45;
int a[N];
int l[N],w[N][N],c[N][N];
vector<pair<int,ll> > f[N];
int now[N];
void getmax(pair<int,ll> &x,pair<int,ll> y){
    if(x.first>y.first)x=y;
    else if(x.first==y.first)x.second+=y.second;
}
signed main(){
    read(n);
    fo(i,1,n){
        read(a[i]);
    }
    fo(i,0,n){
        fo(j,i+1,n){
            c[i][++l[i]]=a[j];
        }
        c[i][++l[i]]=n+1;
        sort(c[i]+1,c[i]+1+l[i]);
        int t=1;
        fo(j,1,l[i]){
            w[i][j]=t;
            t*=c[i][j]-c[i][j-1];
        }
        f[i]=vector<pair<int,ll>>(t,{1e9,0});
    }
    f[0][0]={0,1};
    fo(i,0,n-1){
        int at=0;
        fo(j,1,l[i])if(c[i][j]==a[i+1])at=j;
        fu(j,0,f[i].size()){
            int t=j;
            fd(k,l[i],1){
                now[k]=t/w[i][k];
                t%=w[i][k];
            }
            int cnt=0;
            fo(k,at+1,l[i])cnt+=now[k];
            int t1=0,t2=0;
            fo(k,1,at-1)t1+=now[k]*w[i+1][k];
            fo(k,at+2,l[i])t1+=now[k]*w[i+1][k-1];
            t2=t1;
            t1+=(now[at]+now[at+1])*w[i+1][at];
            t2+=(now[at]+now[at+1]+1)*w[i+1][at];
            getmax(f[i+1][t1],f[i][j]);
            getmax(f[i+1][t2],{f[i][j].first+cnt,f[i][j].second});          
        }
    }
    fo(i,1,n)write(f[n][i].first,' ',f[n][i].second,'\n');
    return 0;
}