[EC Final 2022] Dining Professors

形式化题目

有一个长度为 $n$ 的环，环上每个位置 $p$ 都正对着编号相同的教授 $p$ 。每个教授能拿到的是自己面前，以及左右相邻两个位置，共 $3$ 个位置上的菜：

text

1
2
3
4
5
6
7        位置 p-1
           |
 教授 p-1 | 教授 p | 教授 p+1
           |
        位置 p+1

教授 i 能访问：位置 i-1、位置 i、位置 i+1（下标模 n）

给出 $b_1,\dots,b_n\in\{0,1\}$ ，其中 $b_i=1$ 表示教授 $i$ 能吃辣。要把 $a$ 盘辣菜和 $n-a$ 盘不辣菜放进这 $n$ 个位置（每个位置恰好一盘）。定义每位教授的满意度：

若 $b_i=1$ ：满意度为 $3$ （能拿到的菜有多少就算多少）。
若 $b_i=0$ ：满意度为三个可达位置中不辣菜的盘数。

求所有教授满意度之和的最大值。

暴力解法

思路

最直白的做法是真正去「摆菜」：由于菜只是辣与不辣两种，摆法完全由「哪些位置放不辣菜」决定。枚举所有大小为 $n-a$ 的位置集合（即枚举哪 $n-a$ 个位置放不辣菜，其余放辣菜），对每种摆法老老实实按定义统计一次满意度，取最大值。

这个做法不需要任何观察，只要把题面翻成代码即可，因此它天然是正确的，适合用来对拍。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 13:15
 *
 * P9728 [EC Final 2022] Dining Professors
 * 暴力解：辣菜之间没有区别、不辣菜之间也没有区别，
 *         于是只需枚举「哪 n-a 个位置放不辣菜」这 C(n, n-a) 种情况，
 *         对每种情况老老实实按定义统计满意度，取最大值。
 *         只适合 n<=20 左右的小数据，用于对拍。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int n;   // 教授人数 = 位置数
int a;   // 辣菜数量
int b[maxn];  // b[i]=1:教授 i 能吃辣
int pos[maxn]; // pos[p]=1:位置 p 放的是不辣菜

ll best; // 当前找到的最大满意度

// dep:      正在决定第 dep 个位置
// spicyCnt: 已经放掉的辣菜数量
void dfs(int dep, int spicyCnt) {
    // 剩下的位置全放辣菜也不够 n-a 道不辣菜，剪枝
    if (spicyCnt > a) {
        return;
    }
    if (dep == n) {
        if (spicyCnt != a) {
            return;
        }
        ll tot = 0;
        for (int i = 0; i < n; ++i) {
            int l = (i - 1 + n) % n; // 左边位置
            int r = (i + 1) % n;     // 右边位置
            if (b[i] == 1) {
                tot += 3;            // 能吃辣：三盘菜都算满意
            } else {
                tot += pos[l] + pos[i] + pos[r]; // 不能吃辣：只数不辣菜
            }
        }
        if (tot > best) {
            best = tot;
        }
        return;
    }
    // 位置 dep 放辣菜
    pos[dep] = 0;
    dfs(dep + 1, spicyCnt + 1);
    // 位置 dep 放不辣菜
    pos[dep] = 1;
    dfs(dep + 1, spicyCnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a;
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    best = -1;
    dfs(0, 0);
    cout << best << "\n";
    return 0;
}

复杂度

枚举的子集数为 $\binom{n}{n-a}$ ，最坏是 $2^n$ 量级；每种摆法还要 $O(n)$ 统计满意度。总复杂度 $O(2^n\cdot n)$ ，只能处理 $n\leqslant 20$ 左右的小数据。

瓶颈

暴力真正的浪费在于「把不辣菜当成了有区别的 $n-a$ 盘菜」——它枚举的是集合，而不是盘数。换一个角度看：我们真正要决定的只是哪些位置放不辣菜这一个 $0/1$ 选择，一共 $n$ 个位置、要选中恰好 $n-a$ 个。如果能让「选中某个位置」的收益互相独立，那么剩下的就只是排序取前几名了。

另一种朴素的暴力是枚举所有 $n!$ 种「菜的全排列」，那是把同色菜也当成不同的，正确但更慢，这里不采用。

正解

思路

第一步：能吃辣的教授贡献固定。

如果 $b_i=1$ ，无论桌上怎么摆，他都能拿到面前的 $3$ 盘菜，满意度恒为 $3$ 。所以所有 $\sum b_i$ 位能吃辣的教授一共贡献

3\sum_{i=1}^{n} b_i,

这部分与摆法无关，先记作底数，之后只需关心 $b_i=0$ 的教授。

第二步：把「不辣菜放在哪里」写成可加的收益。

记 $x_p\in\{0,1\}$ 表示位置 $p$ 是否放不辣菜（ $x_p=1$ 表示放不辣菜），那么约束只有一个：

\sum_{p=1}^{n} x_p = n-a .

对一位 $b_i=0$ 的教授，他的满意度是 $x_{i-1}+x_i+x_{i+1}$ 。把所有 $b_i=0$ 的教授的满意度加起来，交换求和顺序，改为按「位置」统计：

\sum_{i:\,b_i=0}\bigl(x_{i-1}+x_i+x_{i+1}\bigr) =\sum_{p=1}^{n} x_p\cdot c_p, \qquad c_p=(1-b_{p-1})+(1-b_p)+(1-b_{p+1}).

这里 $c_p$ 的含义非常直观：位置 $p$ 上放一道不辣菜，会让面前以及左右共三位教授各多得 $1$ 分满意度； $c_p$ 就是这三位中「不能吃辣」的人数，也就是这道不辣菜能带来的总收益。

第三步：收益彼此独立，贪心选最大的 $n-a$ 个。

关键点在于： $c_p$ 只由 $b$ 决定，是一个常数；而 $x_p$ 之间没有任何别的耦合约束，唯一的限制是「恰好选 $n-a$ 个位置」。于是目标函数是 $x$ 的线性函数，约束只是个数限制。此时选收益最大的 $n-a$ 个位置一定最优：对任意可行的 $x$ ，其收益 $\sum_p x_p c_p$ 不可能超过 $c$ 中前 $n-a$ 大的那些值之和（否则把被选中的某个小收益位置换成未选中的更大收益位置，收益只会变大，与最优性矛盾）。而这个上界又是可达的——把那 $n-a$ 个位置放上不辣菜即可，所以贪心既是上界又能构造出摆法。

具体实现就是把 $c_1,\dots,c_n$ 从大到小排序，取前 $n-a$ 项求和，再加上底数 $3\sum b_i$ 。

样例走一遍。 $n=5,a=2,b=(1,0,1,0,1)$ 。底数 $3\sum b_i=3\times 3=9$ ，需要放 $n-a=3$ 道不辣菜。逐个位置算收益：

位置 $p$	三位相关教授 $b_{p-1},b_p,b_{p+1}$	其中 $b=0$ 的个数 $c_p$
0	$b_4,b_0,b_1=1,1,0$	1
1	$b_0,b_1,b_2=1,0,1$	1
2	$b_1,b_2,b_3=0,1,0$	2
3	$b_2,b_3,b_4=1,0,1$	1
4	$b_3,b_4,b_0=0,1,1$	1

排序后前 $3$ 大为 $2,1,1$ ，和是 $4$ ，答案 $9+4=13$ ，与样例一致。（其中一个最优摆法是把不辣菜放在位置 $2$ 及其两侧之一，再随便一个位置。）

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 13:15
 *
 * P9728 [EC Final 2022] Dining Professors
 * 正解：每个位置放一道不辣菜，对总满意度的增益 = (1-b[i-1])+(1-b[i])+(1-b[i+1]);
 *       辣菜放到任何位置都不贡献，因此把 n-a 道不辣菜放到增益最大的 n-a 个位置。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5 + 5;

int n;   // 教授人数 = 位置数
int a;   // 辣菜数量
int b[maxn]; // b[i]=1:教授 i 能吃辣; b[i]=0:教授 i 不能吃辣
int c[maxn]; // c[p]:在位置 p 放一道不辣菜带来的满意度增益

void read_data() {
    cin >> n >> a;
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();

    // 能吃辣的教授：无论摆什么菜都是 3 道菜可吃，先把这部分作为底数
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (b[i] == 1) {
            ans += 3;
        }
    }

    // 对不能吃辣的教授，只有不辣菜才算满意
    // 位置 p 摆在教授 p-1、p、p+1 面前，所以一道不辣菜影响这三位教授
    for (int p = 0; p < n; ++p) {
        int l = (p - 1 + n) % n; // 左边教授
        int r = (p + 1) % n;     // 右边教授
        c[p] = (1 - b[l]) + (1 - b[p]) + (1 - b[r]);
    }

    // 一共要选 n-a 个位置放不辣菜，贪心选增益最大的那些
    sort(c, c + n, greater<int>());
    for (int k = 0; k < n - a; ++k) {
        ans += c[k];
    }

    cout << ans << "\n";
    return 0;
}

复杂度

计算 $c$ 与求和都是 $O(n)$ ，排序是 $O(n\log n)$ ，空间 $O(n)$ 。在 $n\leqslant 10^5$ 下轻松通过。

总结

先抽出与摆法无关的常量：能吃辣的教授恒贡献 $3$ 。
再用贡献法换视角：不辣菜放在位置 $p$ 的收益是固定值 $c_p$ ，与其它位置无关。
约束退化成「恰好选 $n-a$ 个位置」后，线性目标 + 个数限制 ⇒ 排序取最大的 $n-a$ 个即可，无需 DP 或匹配。

这道题最容易卡住的地方是看到「环形摆菜」就去做复杂的状态或环形 DP；一旦发现每道不辣菜的收益可以单独计算、彼此不冲突，问题就坍缩成一次排序。