#5462. 「ROI 2012 Day 2」汗国军队 题解

问题分析

我们有 $N$ 个战士（编号 $1$ 到 $N$），其中 $K$ 个是护卫（给定编号）。我们需要计算所有 $N!$ 种排列中，满足**护卫构成最长递增子序列（LIS）**的排列数量。

关键条件：

• 护卫在排列中的位置必须形成递增序列（因为是子序列）
• 这个护卫序列必须是最长的递增子序列
• 即：不存在比护卫序列更长的递增子序列

核心观察

设护卫集合为 $G$，非护卫集合为 $H$。

条件分析

对于排列 $p$，要满足：

1. 护卫递增：护卫在 $p$ 中的位置序列是递增的
2. LIS 长度恰好为 K：整个排列的最长递增子序列长度 = $K$
3. 护卫就是 LIS：存在一个 LIS 恰好包含所有护卫

转化为约束条件

设护卫按编号排序为 $g_1 < g_2 < \cdots < g_K$。

在排列中，必须满足：

• $g_1$ 出现在 $g_2$ 之前，$g_2$ 出现在 $g_3$ 之前，...
• 对于任意非护卫 $h$，不能与护卫形成更长的递增序列

动态规划解法

状态设计

由于 $N \leq 15$，可以使用状态压缩 DP。

设 $dp[mask][last]$ 表示：

• 已经放置了集合 $mask$ 中的战士
• 最后一个放置的护卫编号是 $last$（如果是护卫）或特殊值（如果不是护卫）

但这样状态数太多：$2^N \times (K+1)$ 可能达到 $2^{15} \times 16 \approx 500,000$。

更高效的状态设计

关键观察：我们只关心护卫的相对位置关系。

设 $dp[mask][i]$ 表示：

• 已经放置了集合 $mask$ 中的战士
• 当前已放置的护卫形成了护卫序列的前 $i$ 个

状态转移：

• 如果下一个放护卫 $g_{i+1}$：必须满足 $g_{i+1} >$ 上一个护卫
• 如果下一个放非护卫 $h$：必须满足 $h$ 不会与已放置护卫形成更长的序列

算法实现

状态定义

令 $dp[S][i]$ = 放置了集合 $S$ 中的战士，且已放置了前 $i$ 个护卫的方案数。

边界：$dp[0][0] = 1$

转移：

1. 放置下一个护卫：如果 $i < K$ 且 $g_{i+1} \notin S$，则：

   $$dp[S \cup \{g_{i+1}\}][i+1] += dp[S][i]$$

   条件是：新护卫 $g_{i+1}$ 必须大于前一个护卫（自动满足，因为护卫编号递增）

2. 放置非护卫：对于所有 $h \notin S$ 且 $h \notin G$：

   • 需要检查 $h$ 不会破坏 LIS 条件
   • 具体来说：$h$ 不能插入到护卫序列的任何位置形成更长的递增序列

检查非护卫合法性

放置非护卫 $h$ 时，必须满足：

• 如果 $h < g_1$：只能放在 $g_1$ 之前
• 如果 $g_i < h < g_{i+1}$：只能放在 $g_i$ 和 $g_{i+1}$ 之间
• 如果 $h > g_K$：只能放在 $g_K$ 之后

更精确地说：$h$ 必须放在护卫序列的"正确区间"内，不能形成更长的 LIS。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> guards(K);
    for (int i = 0; i < K; i++) {
        cin >> guards[i];
    }
    
    // 标记护卫
    vector<bool> is_guard(N + 1, false);
    for (int g : guards) {
        is_guard[g] = true;
    }
    
    // 非护卫列表
    vector<int> others;
    for (int i = 1; i <= N; i++) {
        if (!is_guard[i]) {
            others.push_back(i);
        }
    }
    
    // 状态压缩DP
    int total_states = 1 << N;
    vector<vector<long long>> dp(total_states, vector<long long>(K + 1, 0));
    dp[0][0] = 1;
    
    for (int mask = 0; mask < total_states; mask++) {
        for (int i = 0; i <= K; i++) {
            if (dp[mask][i] == 0) continue;
            
            // 尝试放置下一个护卫
            if (i < K) {
                int next_guard = guards[i];
                if (!(mask & (1 << (next_guard - 1)))) {
                    int new_mask = mask | (1 << (next_guard - 1));
                    dp[new_mask][i + 1] += dp[mask][i];
                }
            }
            
            // 尝试放置非护卫
            for (int h : others) {
                if (mask & (1 << (h - 1))) continue;
                
                // 检查h是否可以放在当前位置
                bool valid = true;
                
                if (i == 0) {
                    // 还没有放任何护卫，h必须小于第一个护卫
                    if (K > 0 && h > guards[0]) {
                        valid = false;
                    }
                } else if (i == K) {
                    // 所有护卫都已放置，h必须大于最后一个护卫
                    if (h < guards[K - 1]) {
                        valid = false;
                    }
                } else {
                    // 有部分护卫已放置，h必须在当前护卫和下一个护卫之间
                    if (h < guards[i - 1] || h > guards[i]) {
                        valid = false;
                    }
                }
                
                if (valid) {
                    int new_mask = mask | (1 << (h - 1));
                    dp[new_mask][i] += dp[mask][i];
                }
            }
        }
    }
    
    cout << dp[total_states - 1][K] << endl;
    
    return 0;
}

复杂度分析

• 状态数：$O(2^N \times K)$
• 转移：每个状态尝试 $N$ 种选择
• 总复杂度：$O(2^N \times N \times K)$
• 对于 $N \leq 15$，$2^{15} \times 15 \times 15 \approx 7 \times 10^6$，可接受