P14364 [CSP-S 2025] 员工招聘 / employ 笔记

考完这次 CSP 真正的感受到了自己的弱小，「努力」了大半年，面对正赛题解还是跟读天书一样，什么都看不懂，文化课成绩倒是步步低降了。

我该在哪里停留？我问我自己。

---

设最终的排列是 $p_{1\dots n}$，$[1,i)$ 拒绝了 $b_i$ 个人，分析一下最终的排列如何进行判定。

• 情况 A：$s_i=0$，此时 $p_i$ 可以是任意数，对答案无影响。
• 情况 B：$s_i=1$，但是 $p_i$ 不满意，已经跑了，即 $c_{p_i}\le b_i$。
• 情况 C：$s_i=1$，$p_i$ 正常参加考试，即 $c_{p_i}>b_i$。

好像这些判定中，只有 $b_i$ 是未知的，所以是不是设 $f_{i,j}$ 表示 $b_i=j$ 的方案数即可？然后就会发现 $b_i$ 单调不降。前面的情况 A,C 的选择，会对后面的情况 B 产生影响，并且很难记录。

因此考虑最后再处理情况 A,C 的选择，如果只用考虑情况 A 的选择，那么只需记录 $k$ 表示有 $k$ 个位置不是情况 A，$(n-k)!$ 就是情况 A 的选择。

接着是考虑情况 C 的选择，要求情况 C 全部是 $c_{p_i}>b_i$ 的方案数，等价于情况 C 任意选，减去情况 C 中有 $c_{p_i}\le b_i$ 的方案数，由于刷表法 DP 从左往右确定每一个位置，因此选择容斥，即「至少」与「恰好」的转换。

设 $f_{i,j,k,l}$ 表示 $b_i=j$，且前 $i$ 个数中有 $k$ 个位置是情况 B，至少 $l$ 个位置是情况 C，并且至少有这 $l$ 个位置满足是 $c_{p_i}\le b_i$ 的情况 C。

设 ${\mathrm{cnt}}_x$ 表示耐心值小于等于 $x$ 的人数。

情况 A 的转移：

$$f_{i,j,k,l}\to f_{i+1,j+1,k,l}$$

情况 B 的转移：

$$f_{i,j,k,l}\times ({\mathrm{cnt}}_j-k-l)\to f_{i+1,j,k+1,l}$$

情况 C，这个位置任意选的转移：

$$f_{i,j,k,l}\to f_{i+1,j,k,l}$$

情况 C，这个位置确定满足 $c_{p_i}\le b_i$ 的转移：

$$-f_{i,j,k,l}\times ({\mathrm{cnt}}_j-k-l)\to f_{i+1,j,k,l+1}$$

发现 $k+l\le n$ 且可以合并，$i$ 可以滚动数组，状态数 $O(n^3)$，转移 $O(1)$，时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

答案就是 $\sum _{i=0}^{n-m}\sum _{j=0}^n{f}_{n,i,j}(n-j)!$。