「一本通 5.4 练习 3」动物园

GitHub跳转原题关系图返回列表

把每个小朋友只依赖的连续 5 个围栏压成 32 种窗口状态，滑动时右移补位并在窗口起点结算得分，最后枚举初窗口的 32 种取值破环取最大。

OJ: roj

题目 ID: 1596

难度:提高

标签:动态规划状态压缩环形DPpython

创建: 2026-09-30 20:56

更新: 2026-10-07 13:50

前置题目

roj 1593「一本通 5.4 例 2」牧场的安排B 沿用 A 教的「按推进方向分段、把影响未来的局部信息压成掩码、只保留最近窗口做滚动 DP」这一状态设计：A 用行掩码只记相邻两行，B 换成 5 位窗口状态只记最近 5 个围栏，再叠加按窗口起点结算得分与枚举初窗口破环。

形式化题目

$N$ 个围栏编号 $1, 2, \ldots, N$ 顺时针围成一圈，每个围栏里的动物可以保留或移走。把「保留」记作 $1$ 、「移走」记作 $0$ ，就得到一个环形 0/1 序列 $b_1, b_2, \ldots, b_N$ 。

有 $C$ 个小朋友，第 $k$ 个小朋友能看到从 $E_k$ 起顺时针连续的 5 个围栏（越过 $N$ 则从 $1$ 续），并给出两个集合：害怕集合 $A_k$ 与喜欢集合 $L_k$ ，两者都是这 5 个围栏编号的子集且互不相交。第 $k$ 个小朋友高兴当且仅当

\bigl(\exists\, i \in A_k:\ b_i = 0\bigr) \quad \lor \quad \bigl(\exists\, j \in L_k:\ b_j = 1\bigr),

即「至少一个害怕的动物被移走」或「至少一个喜欢的动物被保留」。求高兴人数最大可能的取值。

其中 $10 \leqslant N \leqslant 10^4$ ， $1 \leqslant C \leqslant 5 \times 10^4$ 。

以样例 1 的第三个小朋友（ $E = 6$ ）为例：他害怕围栏 $9$ 、喜欢围栏 $6$ 与 $8$ 。只要 $b_9 = 0$ ，或 $b_6 = 1$ ，或 $b_8 = 1$ ，他就高兴；唯一让他不高兴的取值是 $b_9 = 1$ 、 $b_6 = b_8 = 0$ 。

正解

思路

朴素做法及其瓶颈。 最直接的想法是枚举 $2^N$ 种留/移方案，对每种方案扫一遍全部 $C$ 个小朋友统计高兴人数，复杂度 $O(2^N C)$ 。 $N$ 最大 $10^4$ ，完全不可行。瓶颈在于它把 $N$ 个围栏当成彼此独立的决策，而题面其实给了一个很强的结构性事实：每个约束只依赖连续 5 个围栏。这意味着每个围栏的影响半径是有限的——当我们的视线沿着环向前推进，一个围栏离开「最近 5 个围栏」的窗口后，它就再也不会出现在任何尚未结算的约束里了。

把连续 5 个围栏压成状态。 既然任何时刻只有 5 个围栏的取值会影响未来，那就只记住它们。定义窗口状态 $s$ 为一个 5 位掩码，第 $j$ 位（ $j = 0, \ldots, 4$ ）表示窗口起点后第 $j$ 个围栏是否保留动物。共有 $2^5 = 32$ 种状态。

窗口沿环前进一步时，起点处的那个围栏离开窗口，新围栏进入窗口末尾。用位运算描述：

s \;\longrightarrow\; s \gg 1 \quad\text{或}\quad s \gg 1 \mid 16.

旧位 $j$ 对应的围栏在新窗口中排在位置 $j - 1$ ，所以整体右移一位；空出的第 4 位交给新围栏，两个分支分别对应把新围栏的动物移走（s >> 1）和保留（s >> 1 | 16，16 = 1 << 4）。

把得分挂在窗口起点上。 一个小朋友的 5 个围栏，在窗口起点恰好等于他的 $E$ 时被完整覆盖，这是他第一次也是唯一一次被完整覆盖。所以得分只需在那一刻结算。把他的两个集合也编码成对齐的 5 位掩码（位 $j$ = 围栏 $E + j$ ），高兴判定就退化成两个按位运算：

\text{高兴} \iff (\texttt{afraid} \;\&\; \sim s) \neq 0 \;\lor\; (\texttt{fond} \;\&\; s) \neq 0.

左边是「有害怕的动物被移走」（ $\sim s$ 是补集），右边是「有喜欢的动物被保留」。于是预计算

\mathrm{gain}[e][s] = \#\{\text{起点为 } e \text{ 的小朋友在取舍 } s \text{ 下高兴}\}.

以样例 1 的前四个窗口起点为例，表中位串从左到右是位 $4 \to$ 位 $0$ ，即「窗口中最后一个围栏 $\to$ 第一个围栏」：

窗口起点 $e$	该起点小朋友的 `afraid` / `fond`	得 1 分的状态数	得 0 分的状态
1	无	0	全部 32 个
2	`00100` / `10001`	28	`00100` `00110` `01100` `01110`
3	`01000` / `00010`	24	`01000` `01001` `01100` `01101` `11000` `11001` `11100` `11101`
4	无	0	全部 32 个

观察重点：得 0 分的状态恰好是「害怕的全留下、喜欢的全移走」的组合。起点 $e = 2$ 的小朋友害怕围栏 $4$ （位 2）、喜欢围栏 $2$ 和 $6$ （位 0、位 4），所以只有 ??1?0 且位 4 为 0、位 0 为 0 的 4 个状态让他不高兴——afraid & ~s 与 fond & s 同时为 0。起点 1 和 4 没有小朋友， 32 个状态一律得 0 分。

沿环递推。 设 $dp[s]$ 是以当前窗口为终点、已结算过的最高得分，则每前进一个窗口：

dp'[t] = \max_{s \to t} \bigl(dp[s]\bigr) + \mathrm{gain}[e][t],

其中 $e$ 是新窗口的起点， $s \to t$ 是上面两条转移。这是一个标准的「窗口 + 最大值」递推，每步只处理 32 个状态、64 条转移。

破环。 环上没有天然的「第一个围栏」。处理办法是枚举第 1 个窗口（围栏 $1 \sim 5$ ）的全部 32 种状态 first，把环拆成 32 条链：

初值 $dp[\texttt{first}] = \mathrm{gain}[1][\texttt{first}]$ ，其余状态为 $-\infty$ ；
窗口起点依次推到 $2, 3, \ldots, N$ ，每步按上面的递推更新；
再做一次不带得分的平移，窗口回到起点 $1$ （此时覆盖围栏 $N+1 \sim N+5$ ，模 $N$ 后正是 $1 \sim 5$ ）；
只有 $dp[\texttt{first}]$ 才代表首尾吻合的合法环形安排，取 32 次枚举的最大值即答案。

第 3 步不计分，是因为起点 1 的那批小朋友在第 1 步已经算过；代码里给 gain 末尾追加一行全 $0$ 来实现这次纯平移。又因为 $N \geqslant 10 > 5$ ，窗口前进 $N$ 步后不会和自己重叠，「起点 $N+1$ 」确实是一组完好的 5 个围栏 $1 \sim 5$ ，第 4 步可以直接比较整个 5 位状态。

样例 1 取 first = 00000（围栏 $1 \sim 5$ 的动物全移走）时， $N$ 步累计分的最优值序列为

1,\ 2,\ 2,\ 2,\ 3,\ 3,\ 4,\ 4,\ 4,\ 4,\ 5,\ 5,\ 5,\ 5,

终值 $dp[\texttt{00000}] = 5$ ，即 5 个小朋友全部高兴，与样例输出一致。序列的台阶恰好落在 5 个小朋友的 $E$ 上：分数在窗口起点 $2, 3, 6, 8, 12$ 处各涨一次，正是 5 个小朋友的起始围栏，直观验证了「每个小朋友只在自己的窗口起点被结算一次」。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 21:05
# update_at: 2026-09-30 21:05

import sys

WINDOW = 5
STATES = 1 << WINDOW  # 窗口状态数：5 个围栏各「留 / 移」两种，共 32 种
NEG = -1 << 60        # 不可达状态的初值，比任何合法答案都小


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    fence = next(data)
    kids = next(data)

    # 按小朋友看到的起始围栏 E 分桶，桶里存 (害怕集合, 喜欢集合) 的 5 位掩码，
    # 位 j 表示他视野里第 j 个围栏（即编号 E+j），1 表示该围栏出现在对应名单里。
    by_start: list[list[tuple[int, int]]] = [[] for _ in range(fence + 1)]
    for _ in range(kids):
        start = next(data)
        feared = next(data)
        liked = next(data)
        # 围栏编号绕圈回绕：(编号 - E) mod N 就是它在窗口内的下标
        afraid = 0
        for _ in range(feared):
            afraid |= 1 << ((next(data) - start) % fence)
        fond = 0
        for _ in range(liked):
            fond |= 1 << ((next(data) - start) % fence)
        by_start[start].append((afraid, fond))

    # gain[e][s]：起始围栏为 e、5 位保留情况为 s 时，能高兴的小朋友数。
    # 高兴 <=> 有害怕的动物被移走 (afraid & ~s) 或 有喜欢的动物被留下 (fond & s)。
    # 位 j 对齐，故 s 可直接与两个掩码按位运算。
    # 末尾多出一行全 0：窗口滑到起点 N+1（就是起点 1）时只做平移、不重复计分。
    gain = [
        [sum(1 for afraid, fond in by_start[e] if afraid & ~s or fond & s) for s in range(STATES)]
        for e in range(1, fence + 1)
    ] + [[0] * STATES]

    # next_s: 窗口状态从 s 滑动一格后的两个候选（新围栏的动物留 / 移）。
    # 位 j 记录围栏 pos+j，滑动后旧位 j 变成新位 j-1，新位 4 就是刚进视野的围栏。
    next_s = [(s >> 1, s >> 1 | 16) for s in range(STATES)]

    best = 0
    # 圆环没有天然起点，只能枚举第 1 个窗口的 5 位状态；滑 N 格后必须回到同一个状态。
    for first in range(STATES):
        cur = [NEG] * STATES
        cur[first] = gain[0][first]  # gain[0] 对应起始围栏 1
        # 起点 1 已作为初值算过，再滑 N 次：前 N-1 次补齐起点 2..N，最后一次不带分回到起点 1。
        for row in gain[1:]:
            nxt = [NEG] * STATES
            for s, val in enumerate(cur):
                if val == NEG:
                    continue
                for t in next_s[s]:
                    cand = val + row[t]
                    if cand > nxt[t]:
                        nxt[t] = cand
            cur = nxt
        if cur[first] > best:  # 绕回起点，只有状态吻合的方案才是合法的圆环安排
            best = cur[first]

    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148/**
 * 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-05 11:52
 * update_at: 2026-10-05 11:52
 */
// main.cpp：环形状态压缩 DP 求解最多高兴的小朋友数。
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 10005;      // 围栏数上限
const int MAXC = 50005;      // 小朋友数上限
const int STATES = 32;       // 连续 5 个围栏的留/移状态数 2^5
const int NEG = -1000000000; // 不可达状态的初值，比任何合法得分都小

ll fence_n;  // 围栏数 N
ll child_cnt; // 小朋友数 C

int head[MAXN];        // head[e]：起始围栏为 e 的小朋友链表头
int nxt_child[MAXC];   // 小朋友链表的后继
int afraid_mask[MAXC]; // 该小朋友害怕的围栏在窗口内的 5 位掩码，位 j 对应围栏 e+j
int fond_mask[MAXC];   // 该小朋友喜欢的围栏在窗口内的 5 位掩码
int edge_cnt;

int gain[MAXN][STATES]; // gain[e][s]：窗口起点为 e、5 位保留情况为 s 时高兴的小朋友数

int cur[STATES];    // 当前窗口状态的最高得分
int next_dp[STATES]; // 窗口右移一格后的最高得分

// 把小朋友挂到起点 e 的链表上。
void add_child(ll e, int afraid, int fond) {
    edge_cnt++;
    afraid_mask[edge_cnt] = afraid;
    fond_mask[edge_cnt] = fond;
    nxt_child[edge_cnt] = head[e];
    head[e] = edge_cnt;
}

// 预计算 gain 表：只在小朋友视野起点处结算一次得分。
void build_gain() {
    for (ll e = 1; e <= fence_n; e++) {
        for (int s = 0; s < STATES; s++) {
            int cnt = 0;
            for (int i = head[e]; i != 0; i = nxt_child[i]) {
                // 高兴：有害怕的动物被移走（掩码位为 0）或有喜欢的动物被保留（掩码位为 1）。
                if ((afraid_mask[i] & ~s) != 0 || (fond_mask[i] & s) != 0) {
                    cnt++;
                }
            }
            gain[e][s] = cnt;
        }
    }
}

void read_input() {
    cin >> fence_n >> child_cnt;
    for (ll k = 1; k <= child_cnt; k++) {
        ll e, f, l;
        cin >> e >> f >> l;
        int afraid = 0;
        for (ll j = 1; j <= f; j++) {
            ll x;
            cin >> x;
            ll idx = ((x - e) % fence_n + fence_n) % fence_n; // 围栏编号换算成窗口内下标 0..4
            afraid |= 1 << idx;
        }
        int fond = 0;
        for (ll j = 1; j <= l; j++) {
            ll y;
            cin >> y;
            ll idx = ((y - e) % fence_n + fence_n) % fence_n;
            fond |= 1 << idx;
        }
        add_child(e, afraid, fond);
    }
}

void solve() {
    int best = 0;
    // 圆环没有天然起点，枚举第 1 个窗口的 32 种取值，滑 N 格后要求状态回到同一个。
    for (int first = 0; first < STATES; first++) {
        for (int s = 0; s < STATES; s++) {
            cur[s] = NEG;
        }
        cur[first] = gain[1][first];

        // 窗口起点从 2 推到 N，每步右移一格并结算该起点的小朋友。
        for (ll e = 2; e <= fence_n; e++) {
            for (int s = 0; s < STATES; s++) {
                next_dp[s] = NEG;
            }
            for (int s = 0; s < STATES; s++) {
                if (cur[s] == NEG) {
                    continue;
                }
                int base = cur[s];
                int t = s >> 1; // 新进视野的围栏把动物移走
                if (base + gain[e][t] > next_dp[t]) {
                    next_dp[t] = base + gain[e][t];
                }
                t = (s >> 1) | 16; // 新进视野的围栏保留动物，16 = 1 << 4
                if (base + gain[e][t] > next_dp[t]) {
                    next_dp[t] = base + gain[e][t];
                }
            }
            for (int s = 0; s < STATES; s++) {
                cur[s] = next_dp[s];
            }
        }

        // 再做一次不带得分的平移：窗口回到起点 1（起点 N+1 模 N 后为 1），避免重复计分。
        for (int s = 0; s < STATES; s++) {
            next_dp[s] = NEG;
        }
        for (int s = 0; s < STATES; s++) {
            if (cur[s] == NEG) {
                continue;
            }
            int t = s >> 1;
            if (cur[s] > next_dp[t]) {
                next_dp[t] = cur[s];
            }
            t = (s >> 1) | 16;
            if (cur[s] > next_dp[t]) {
                next_dp[t] = cur[s];
            }
        }
        // 只有首尾状态吻合的方案才对应合法的圆环安排。
        if (next_dp[first] > best) {
            best = next_dp[first];
        }
    }
    cout << best << "\n";
}

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

    read_input();
    build_gain();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(32C + 2048N)$ 。预计算 gain 需要对每个窗口起点、每个状态扫该起点的小朋友，而所有起点的小朋友数之和为 $C$ ，故为 $O(32C)$ ；DP 为 32 次枚举 $\times\ N$ 步 $\times\ 32$ 个状态 $\times\ 2$ 条转移。 $N = 10^4,\ C = 5 \times 10^4$ 时约 $2 \times 10^7$ 次内层操作，最大数据实测约 0.9 s。
空间复杂度： $O(32N + C)$ 。gain 表为 $(N+1) \times 32$ 个整数，by_start 共 $C$ 个二元组， DP 数组只有 32 项；峰值实测约 15 MB，远低于 128 MB。

总结

题面给出的关键结构是每个约束只依赖连续 5 个围栏。这直接把「 $2^N$ 枚举」压成「 $O(N)$ 次窗口滑动」，状态数只有 $2^5 = 32$ 。
局部性的用法是双向的：向前看只用 5 位状态（转移），向后看则可以在窗口滑过时一次性结算 该起点的小朋友（得分），两者合起来才把每个小朋友不重不漏地计入一次。
环形问题的通用套路是枚举初窗口破环： $N \geqslant 10 > 5$ 时窗口不会自我重叠，枚举第 1 个窗口的 32 种取值、要求首尾状态吻合，就能在 32 条链上取最大。
掩码编码让「高兴判定」变成 afraid & ~s or fond & s 两个按位运算，避免了在热循环里逐条遍历小朋友的名单。

【题目描述】

原题来自：APIO 2007

新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一种动物。如下图所示：

你是动物园的公关主管。你要做的是，让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物，而有些小朋友则害怕某些动物。例如， Alex 喜欢可爱的猴子和考拉，而害怕拥有锋利牙齿的狮子。而 Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。

你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多，否则留给小朋友们观赏的动物就所剩无几了。

每个小朋友站在大围栏圈的外面，可以看到连续的 $5$ 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：

1、至少有一个他害怕的动物被移走；

2、至少有一个他喜欢的动物没被移走。

例如，考虑下图中的小朋友和动物：

假如你将围栏 $4$ 和 $12$ 的动物移走。Alex 和 Ka-Shu 将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴，因为他喜欢的围栏 $6$ 和 $8$ 中的动物都保留了。但是，Polly 和 Hwan 将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。

现在换一种方法，如果你将围栏 $4$ 和 $6$ 中的动物移走，Alex 和 Polly 将很高兴，因为他们害怕的动物被移走了。Chaitanya 也会高兴，虽然他喜欢的动物 $6$ 被移走了，他仍可以看到围栏 $8$ 里面他喜欢的动物。同样的 Hwan 也会因可以看到自己喜欢的动物 $12$ 而高兴。唯一不高兴的只有 Ka-Shu。

如果你只移走围栏 $13$ 中的动物，Ka-Shu 将高兴，因为有一个他害怕的动物被移走了，Alex, Polly, Chaitanya 和 Hwan 也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有 $5$ 个小朋友会高兴。这种方法使得了最多的小朋友高兴。

【输入】

输入的第一行包含两个整数 $N, C$ ，用空格分隔。 $N$ 是围栏数， $C$ 是小朋友的个数。围栏按照顺时针的方向编号为 $1,2,3,…,N$ 。

接下来的 $C$ 行，每行描述一个小朋友的信息，以下面的形式给出： $E\\ F\\ L\\ X\_1 \\ X\_2 \\ \\cdots X\_F \\ Y\_1 \\ Y\_2\\ \\cdots Y\_L$ 。

其中 $E$ 表示这个小朋友可以看到的第一个围栏的编号，换句话说，该小朋友可以看到的围栏为 $E, E+1, E+2, E+3, E+4$ 。注意，如果编号超过 $N$ 将继续从 $1$ 开始算。如：当 $N=14, E=13$ 时，这个小朋友可以看到的围栏为 $13,14,1, 2$ 和 $3$ 。

$F$ 表示该小朋友害怕的动物数。 $L$ 表示该小朋友喜欢的动物数。

围栏 $X\_1, X\_2, \\cdots , X\_F$ 中包含该小朋友害怕的动物。围栏 $Y\_1, Y\_2,\\cdots , Y\_L$ 中包含该小朋友喜欢的动物。

$X\_1, X\_2, \\cdots , X\_F, Y\_1, Y\_2, \\cdots , Y\_L$ 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。

【输出】

仅输出一个数，表示最多可以让多少个小朋友高兴。

小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的 $E$ 对应的小朋友排在第一个，最大的 $E$ 对应的小朋友排在最后一个）。

注意可能有多于一个小朋友对应的 $E$ 是相同的。

【输入样例】

text

1
2
3
4
5
614 5
2 1 2 4 2 6
3 1 1 6 4
6 1 2 9 6 8
8 1 1 9 12
12 3 0 12 13 2

【输出样例】

text

【提示】

样例说明 1

样例 $1$ 给出了前面描述的示例情形。它使得所有小朋友（ $C=5$ ）高兴。

样例输入 2

text

1
2
3
4
5
6
7
812 7
1 1 1 1 5
5 1 1 5 7
5 0 3 5 7 9
7 1 1 7 9
9 1 1 9 11
9 3 0 9 11 1
11 1 1 11 1

样例输出 2

text

样例说明 2

样例 $2$ 给出了这样的情形，要使得所有小朋友（ $C=7$ ）都高兴是不可能的。

数据范围与提示：

对于每一个测试点，如果你的答案正确，则该测试点得满分，否则得 $0$ 分。

对于全部数据， $10≤N≤10^4 ,1≤C≤5×10^4 ,1≤E≤N$ 。

【来源】

一本通在线评测

「一本通 5.4 练习 3」动物园

目录

形式化题目

正解

思路

代码

复杂度

总结