问题理解

我们有 $N$ 个座位排成一行，每个座位对应一个乘客，每个乘客属于 $G$ 个登船组之一。
我们可以：

1. 决定 组的登船顺序（哪个组先登，哪个组后登）
2. 决定 每个乘客从前面登船还是从后面登船

登船规则：

• 按组登船，组内乘客登船顺序 随机等概率
• 乘客从船头或船尾进入，沿过道走到自己的座位，过程中如果经过已经坐下的乘客，就会产生一次“经过”

目标：
最小化 所有可能情况下的平均经过次数（即期望值）。

---

关键观察

1. 冲突的产生条件

两个乘客 $i$ 和 $j$ 会产生“经过”当且仅当：

• 他们从 同一端 登船
• 他们的座位在登船方向上 相反顺序（即靠近入口的先坐下，靠里的后坐下）
• 他们属于 同一个组 或者 先登船的人所属的组在后登船的人所属的组之前登船

更精确地说：

• 如果 $i$ 和 $j$ 从同一端登船，且 $i$ 的座位比 $j$ 更靠近该入口
• 如果 $i$ 在 $j$ 之后 登船，则 $j$ 会经过 $i$（因为 $i$ 已经坐在靠外的位置）
• 但这种情况只会在他们登船顺序满足组顺序约束时发生

2. 组顺序的影响

如果组 $A$ 在组 $B$ 之前登船：

• $A$ 组乘客坐下时，$B$ 组乘客还没登船，所以 $B$ 组乘客不会挡住 $A$ 组乘客
• 但 $A$ 组乘客可能挡住 $B$ 组乘客（如果座位位置和登船方向合适）

3. 登船方向的分配

对于任意两个乘客 $i$ 和 $j$，如果 $i$ 的座位在 $j$ 的左边：

• 让他们从不同端登船，就能避免互相经过的可能性
• 但如果他们属于同一个组，由于组内顺序随机，仍然可能产生经过

---

期望的计算

考虑两个乘客 $i$ 和 $j$（$i < j$，即 $i$ 的座位在 $j$ 的左边）：

情况 1：不同组

• 如果他们从不同端登船：永远不会互相经过
• 如果从同一端登船：
  • 从前端登船：只有 $j$ 在 $i$ 之前登船时，$j$ 会经过 $i$
  • 从后端登船：只有 $i$ 在 $j$ 之前登船时，$i$ 会经过 $j$
  • 发生这种情况的概率取决于他们组的登船顺序

情况 2：同组

• 无论从哪端登船，组内随机顺序都会以 $1/2$ 的概率产生一次经过（如果座位相邻且从同一端登船）

---

问题转化

我们可以将问题转化为：

• 将座位序列分成若干 连续段，每个段内的乘客从同一端登船
• 段与段之间可以安排不同的登船端
• 组的登船顺序也会影响不同段之间的冲突

实际上，最优策略通常是：

• 将座位序列分成两个部分：左边部分从前端登船，右边部分从后端登船
• 分割点的位置和组的登船顺序共同决定了期望值

---

动态规划解法

由于 $G \leq 15$，我们可以用 状态压缩 DP：

状态：
$dp[mask]$ 表示已经安排了登船顺序的组的集合为 $mask$ 时，已产生的最小期望冲突次数。

转移：
从 $mask$ 出发，选择下一个登船的组 $g$，计算将 $g$ 加入时新增的期望冲突：

• $g$ 组内乘客之间的冲突（与已经坐下的本组乘客无关，因为本组同时登船）
• $g$ 组乘客与之前所有组 $mask$ 的乘客之间的冲突

冲突计算：
对于 $g$ 组的一个乘客 $p$ 与 $mask$ 中的一个乘客 $q$：

• 如果 $p$ 和 $q$ 从同一端登船，且 $p$ 的座位在登船方向上在 $q$ 之外
• 并且 $p$ 在 $q$ 之后登船（这里 $q$ 先登船，因为 $q$ 属于 $mask$）
• 那么 $p$ 会经过 $q$，产生 1 次冲突

由于 $g$ 组内顺序随机，$p$ 在 $g$ 组内的登船顺序是随机的，但 $q$ 已经在座位上，所以只要 $p$ 和 $q$ 满足空间和方向条件，就必然产生 1 次冲突。

---

预处理优化

为了高效计算新增冲突，可以预处理：

• $cost[mask][g]$：当已经登船的组集合为 $mask$ 时，新增组 $g$ 会产生的期望冲突次数
• 这可以通过预处理每对乘客 $(i,j)$ 的冲突条件，然后按组聚合得到

具体地，对于 $i$ 在组 $g$，$j$ 在组 $h$：

• 如果 $h \in mask$，且 $i$ 和 $j$ 从同一端登船，且座位位置满足冲突条件
• 那么当 $g$ 加入时，$i$ 会经过 $j$，冲突 +1

由于登船方向是我们优化的，我们需要选择最优的 前后端分配 来最小化总冲突。

---

前后端分配的最优性

对于固定的组顺序，我们可以 独立决定每个乘客从前端还是后端登船 来最小化冲突。

实际上，最优分配是：

• 存在一个分割点 $k$，座位 $1 \dots k$ 从前端登船，座位 $k+1 \dots N$ 从后端登船
• 这个分割点的选择可以最小化组间和组内冲突

因此，在 DP 状态转移时，对于每个 $(mask, g)$，我们枚举所有可能的分割点，计算最小的新增冲突。

---

复杂度分析

• 状态数：$O(2^G)$，$G \leq 15$，可行
• 对于每个状态，枚举下一个组 $O(G)$
• 对于每个 $(mask, g)$，计算最小冲突需要 $O(N)$
• 总复杂度：$O(2^G \cdot G \cdot N)$，在 $N=10^5$ 时可能较大，但通过预处理可以优化

---

总结

这道题的核心是：

1. 将问题分解为 组顺序决策 和 登船方向分配 两个子问题
2. 使用 状态压缩 DP 处理组顺序
3. 对于固定的组顺序，通过 选择最优分割点 来决定登船方向
4. 利用 期望线性性，将总期望分解为每对乘客的冲突概率之和
5. 预处理加速冲突计算

最终得到的最小期望值就是题目要求的答案。