PA 2019 Runda 2 Desant 题解

题目分析

这道题要求我们对于排列的每个子序列长度 $k$，找到逆序对数量最少的子序列，并统计这样的子序列个数。

关键点：

• 输入是一个 $1$ 到 $n$ 的排列
• 需要处理所有 $2^n-1$ 个非空子序列
• $n \leq 40$，不能直接枚举所有子序列

解题思路

核心观察

1. 逆序对与相对顺序：子序列的逆序对数量只取决于元素的相对顺序，与具体数值无关
2. 状态压缩：由于 $n \leq 40$，需要巧妙的状态表示方法
3. 动态规划：利用排列的性质进行状态转移

算法设计

代码采用了一种基于"间隙"的动态规划方法：

状态表示

对于每个前缀 $a[1..i]$，我们维护一个状态，表示当前已选元素的相对位置关系。具体来说：

• siz[i]：前 $i$ 个元素的状态总数
• H[i][j]：第 $i$ 个前缀中第 $j$ 个间隙的大小
• pos[i]：元素 $a[i]$ 在当前排列中的位置

状态转移

对于每个新元素 $a[i]$，有两种选择：

1. 不选：状态直接继承
2. 选：将元素插入到当前排列的某个位置，更新逆序对数量

代码详解

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N = 45;

int n;
int a[N];
int vis[N], siz[N], len[N], H[N][N], A[N], B[N], pos[N];
vector<pii> F[N];  // F[i][j] = {最小逆序对数, 方案数}

// 更新最优解
void U(pii &A, pii B) {
    if (!A.second) {  // 如果A还没有值
        A = B;
        return;
    }
    if (A.first < B.first) return;  // B更差，不更新
    if (A.first == B.first) 
        A.second += B.second;  // 相等，累加方案数
    else 
        A = B;  // B更好，直接替换
}

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    
    // 预处理每个前缀的状态信息
    for (int i = 0; i <= n; i++) {
        // 标记已出现的数字
        for (int j = 1; j <= i; j++)
            vis[a[j]] = 1;
        
        siz[i] = 1;
        int lst = 0;
        len[i] = 0;
        
        // 计算间隙大小
        for (int j = 1; j <= n; j++) {
            if (j == a[i]) 
                pos[i] = len[i] + 1;  // 记录当前元素位置
            
            if (vis[j]) {
                siz[i] *= (j - lst);  // 累积状态数
                H[i][++len[i]] = (j - lst);  // 记录间隙
                lst = j;
            }
        }
        siz[i] *= (n + 1 - lst);
        H[i][++len[i]] = (n + 1 - lst);
        
        // 重置标记
        for (int j = 1; j <= i; j++)
            vis[a[j]] = 0;
    }
    
    // 初始化DP数组
    for (int i = 0; i <= n; i++)
        F[i].resize(siz[i] + 1, {0, 0});
    F[0][0] = {0, 1};  // 初始状态
    
    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < siz[i - 1]; j++) {
            if (!F[i - 1][j].second) continue;
            
            // 解码状态
            int x = j;
            for (int k = 1; k <= len[i - 1]; k++) {
                A[k] = (x % H[i - 1][k]);
                x /= H[i - 1][k];
            }
            
            // 情况1：不选a[i]
            int now = 0;
            for (int k = 1; k <= len[i - 1]; k++) {
                if (k < pos[i] || k > pos[i] + 1)
                    B[++now] = A[k];
                if (k == pos[i] + 1)
                    B[++now] = A[k] + A[k - 1];  // 合并间隙
            }
            
            int P = 0, s = 1;
            for (int k = 1; k <= len[i]; k++) {
                P += B[k] * s;
                s *= H[i][k];
            }
            U(F[i][P], F[i - 1][j]);
            
            // 情况2：选a[i]
            B[pos[i]]++;  // 在pos[i]位置插入元素
            int sum = 0;
            // 计算新增的逆序对
            for (int k = pos[i] + 1; k <= len[i - 1]; k++)
                sum += A[k];
            
            pii qwq = F[i - 1][j];
            qwq.first += sum;  // 加上新增的逆序对
            
            P = 0, s = 1;
            for (int k = 1; k <= len[i]; k++) {
                P += B[k] * s;
                s *= H[i][k];
            }
            U(F[i][P], qwq);
        }
    }
    
    // 输出结果
    for (int i = 1; i < siz[n]; i++)
        printf("%lld %lld\n", F[n][i].first, F[n][i].second);
    
    return 0;
}

算法原理

状态编码

算法将当前已选元素的相对位置编码为一个数字：

• 将 $1$ 到 $n$ 的数字划分为若干连续区间（间隙）
• 每个间隙的大小表示该区间内已选元素的数量
• 状态数等于所有间隙大小的乘积

逆序对计算

当插入一个新元素时：

• 插入位置后面的每个已选元素都会与新元素形成逆序对
• 逆序对数量等于插入位置后面所有间隙中元素数量的总和

样例分析

对于输入：

5
5 3 1 4 2

输出：

0 5  // 长度为1的子序列：都没有逆序对，有5个
0 3  // 长度为2的子序列：有3个子序列没有逆序对  
1 2  // 长度为3的子序列：最小逆序对数为1，有2个
3 1  // 长度为4的子序列：最小逆序对数为3，有1个
7 1  // 长度为5的子序列：就是整个排列，逆序对数为7，只有1个

复杂度分析

• 时间复杂度：$O(n \times \prod \text{间隙大小})$，在 $n=40$ 时可行
• 空间复杂度：$O(n \times \text{状态数})$，使用向量动态分配

总结

这道题的关键在于：

1. 将子序列的相对位置编码为间隙表示
2. 利用动态规划按顺序处理每个元素
3. 在状态转移时高效计算新增的逆序对数量

算法巧妙地利用了排列的性质，通过状态压缩在可接受的时间内解决了 $n=40$ 的大规模问题。