P3622 动物园-状压
[APIO2007] 动物园
题目大意
问题描述：
有一个环形动物园，共有 N 个围栏（环形排列），每个围栏里有一种动物。有 C 个小朋友，每个小朋友会从某个围栏 E 开始，连续看到 5 个围栏（顺时针方向）。
每个小朋友有喜欢的动物和害怕的动物（都在他看到的 5 个围栏中）。
小朋友高兴的条件是：
- 至少有一个他害怕的动物被移走；
- 至少有一个他喜欢的动物没有被移走。
目标： 选择移走哪些动物，使得高兴的小朋友数量最多。
输入格式
N C
E1 F1 L1 X1 X2 ... XF1 Y1 Y2 ... YL1
- 第 1 行：
N（围栏数，10 ≤ N ≤ 10^4），C（小朋友数，1 ≤ C ≤ 5×10^4）。 - 接下来 C 行：每行描述一个小朋友：
E：该小朋友看到的第一个围栏编号（1 ≤ E ≤ N）。F：害怕的动物数。L：喜欢的动物数。- 接着
F个整数：害怕的动物所在围栏编号。 - 接着
L个整数：喜欢的动物所在围栏编号。 - 所有
X和Y都是该小朋友能看到的 5 个围栏中的，且互不相同。
输出格式
一个整数：最多能让多少个小朋友高兴。
解题思路
关键观察
- 每个小朋友只能看到 5 个围栏，这个数字很小，提示我们可以用状态压缩。
- 相邻的小朋友看到的围栏有重叠部分（4 个），因此状态可以传递。
- 由于是环形，首尾状态必须一致（最后 4 个围栏与开头 4 个围栏对应）。
状态设计
用 dp[i][j] 表示处理到第 i 个围栏，且从第 i 个围栏开始的 5 个围栏的状态为 j（二进制表示，1 表示保留，0 表示移走）时，最多能高兴的小朋友数。
状态转移
当前状态的后 4 位必须等于前一个状态的前 4 位（因为重叠）：
dp[j][k] = max(dp[j-1][(k&15)<<1], dp[j-1][(k&15)<<1|1]) + cnt[j][k]
其中 15 的二进制是 1111，用于取后 4 位。
预处理
对于每个小朋友，我们记录他站在位置 st 时，对 5 个围栏的每种状态 j 是否高兴：
- 如果
(害怕的动物集合) ∩ (移走集合) ≠ ∅且(喜欢的动物集合) ∩ (保留集合) ≠ ∅，则该小朋友高兴。 - 预处理
cnt[st][j]表示在位置st，状态为j时高兴的小朋友数。
环形处理
枚举初始状态 i（0 到 31），设置 dp[0][i] = 0，然后进行 DP。最后检查 dp[n][i] 是否与初始状态一致，取最大值。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e4+10;
constexpr int maxm = 3e6+10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;int n,m,ans;
int cnt[maxn][35];
int dp[maxn][35];signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endif // ONLINE_JUDGEscanf("%lld%lld",&n,&m);for(int i=1,st,f,l ;i<=m;++i)// st,fear,love{scanf("%lld%lld%lld",&st,&f,&l);int fear=0;int love=0;for(int j=1,pos ;j<=f;++j){scanf("%lld",&pos);fear |= (1<<(pos-st+n)%n);// 高位离st远}for(int j=1,pos ;j<=l;++j){scanf("%lld",&pos);love |= (1<<(pos-st+n)%n);}for(int j=0;j<32;++j)// 31==0b11111 0-zou 1-liu{if((fear & ~j) || (love & j)){++cnt[st][j];}}}for(int i=0;i<32;++i){memset(dp,128,sizeof(dp[0])*(n+1));dp[0][i]=0;// 0->1for(int j=1;j<=n;++j){for(int k=0;k<32;++k){dp[j][k]=max(dp[j-1][(k&15)<<1],dp[j-1][(k&15)<<1|1])+cnt[j][k];// 15=0b1111,qu hou 4 wei// 取当前的近4位，枚举上个位置的第一位}}ans=max(ans,dp[n][i]);// 1 from 0_i ,n->1 <=> n==0_i}printf("%lld",ans);return 0;
}
复杂度分析
- 时间复杂度：O(N × 32 × 2) = O(64N)，可以通过。
- 空间复杂度：O(N × 32)，在约束范围内。