2025 员工招聘 · 方案一集合记忆化搜索

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1665 字

rec(mask, j) 逐天枚举出场者，2^n·n 状态部分分

2025
计数DP

正文

// CSP-S 2025 复赛 T4 · 员工招聘（方案一：集合记忆化搜索，n ≤ 16 部分分）
// 原题：https://oj.yecheng.tv/p/2469
// 题意：n 名应聘者，面试顺序是一个排列 p。第 i 天题目难度 s_i：
// s_i=1（易）人人都会做，到场者被录用；s_i=0（难）没人会做，
// 到场者被拒绝离场。每个人有耐心上限 c_i：若轮到他之前已有
// 不少于 c_i 人被拒或放弃，他直接放弃参加（同样计入未录用）。
// 求录用人数至少为 m 的排列数，对 998244353 取模。
// （本题在 OJ 上为标准输入输出，无需文件重定向。）
// 思路：
//   每人恰好出场一次，录用人数 = n - 最终被拒/放弃人数，
//   故答案 = 使最终未录用人数 j ≤ n - m 的排列数。
//   记忆化搜索 rec(mask, j)：已出场集合为 mask、当前未录用 j 人
//   时，剩余人的合法排法数。逐天枚举下一位出场者 p：
//   j >= c[p] 则放弃（j 加一）；否则按当天难度录用（j 不变）
//   或被拒（j 加一）。叶子处按 j ≤ n - m 计 1。
// 复杂度：状态 2^n × n，转移 O(n)，n ≤ 16 约 1e8 内可过；满分见方案二。
// 易错点：
//   1. 放弃与被拒都计入「未录用」，比较的是 >= c[p]；
//   2. 录用人数 = n - 未录用数，判定放在叶子而非中途；
//   3. 未录用数最多 n，memo 第二维开 n+2。
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;
int n, m;
char s[20];
int c[20];
ll memo[1 << 16][18];
bool seen[1 << 16][18];

ll rec(int mask, int rej) {
    int day = __builtin_popcount(mask);
    if (day == n) return rej <= n - m ? 1 : 0;
    if (seen[mask][rej]) return memo[mask][rej];
    seen[mask][rej] = true;
    ll &res = memo[mask][rej];
    res = 0;
    for (int p = 0; p < n; p++) {
        if (mask >> p & 1) continue;
        if (rej >= c[p]) { // 耐心不足，放弃参加
            res += rec(mask | 1 << p, rej + 1);
        } else if (s[day] == '1') {
            res += rec(mask | 1 << p, rej); // 录用
        } else {
            res += rec(mask | 1 << p, rej + 1); // 面试但被拒
        }
    }
    return res % MOD;
}

int main() {
    scanf("%d %d %s", &n, &m, s);
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);
    memset(seen, 0, sizeof seen);
    printf("%lld\n", rec(0, 0) % MOD);
    return 0;
}

2025 员工招聘 · 方案一 集合记忆化搜索

正文

CSP-S 标程 · 复赛真题的其它内容

2025 员工招聘 · 方案一集合记忆化搜索