动物园 题解
题目描述
原题来自：APIO 2007
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一种动物。如下图所示：
你是动物园的公关主管。你要做的是，让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事。有些小朋友喜欢某些动物，而有些小朋友则害怕某些动物。例如， Alex 喜欢可爱的猴子和考拉，而害怕拥有锋利牙齿的狮子。而 Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。
你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多，否则留给小朋友们观赏的动物就所剩无几了。
每个小朋友站在大围栏圈的外面，可以看到连续的 \(n\) 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：
- 至少有一个他害怕的动物被移走；
- 至少有一个他喜欢的动物没被移走。
例如，考虑下图中的小朋友和动物：
假如你将围栏 \(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,\dots ,N\) 。
接下来的 \(C\) 行，每行描述一个小朋友的信息，以下面的形式给出：
$ E\ F\ L\ X_1 \ X_2 \dots \ X_F \ Y_1 \ Y_2 \dots Y_L $
其中： \(E\) 表示这个小朋友可以看到的第一个围栏的编号，换句话说，该小朋友可以看到的围栏为 $ E,E+1,E+2,E+3,E+4 $ 。注意，如果编号超过 \(N\) 将继续从 \(1\) 开始算。
\(F\) 表示该小朋友害怕的动物数。
\(L\) 表示该小朋友喜欢的动物数。
围栏 $ X_1 \ X_2 \dots \ X_F $ 中包含该小朋友害怕的动物。围栏
$ \ Y_1 \ Y_2 \dots Y_L $ 中包含该小朋友喜欢的动物。 $ X_1 \ X_2 \dots \ X_F \ Y_1 \ Y_2 \dots Y_L $ 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。
小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的 \(E\) 对应的小朋友排在第一个，最大的 \(E\) 对应的小朋友排在最后一个）。
注意可能有多于一个小朋友对应的 \(E\) 是相同的。
样例输入 1
14 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
样例输出 1
5
数据范围
$ 10 \le N \le 10^4 , 1 \le C \le 5 \times 10^4 ,1 \le E \le N $ 。
思路
真是一道状压好题，只是我当时不会。
当时的想法 $ dp[i][j] $ 表示第 \(i\) 个小朋友，所看到的动物状态为 \(j\)
显然(杜绝显然) \(i\) 和 \(i-1\) 看到的区间是可能重叠的，对于重叠部分，判断如果重叠不同，那么这种转移是不合法的，\(continue\) ，否则判断 \(i\) 区间的小孩能否满意，让他 \(happy\) ，$ dp[i][j]= \max { dp[i-1][k] }+1 $
唯一的问题是这是个环，最靠前和最靠后的小朋友看到的区间可能重合，要保证重叠部分相同才有意义，然后，太难实现，咕了。
正解
$ dp[i][j] $ 表示第 \(i\) 个围栏，向后 \(5\) 个围栏状态为 \(j\) 。
\[dp[i][j]=\max \{ dp[i-1][(j\&15)<<1],dp[i-1][((j\&15)<<1)|1] \} +num[i][j] \]这里的位运算相当巧妙，自行理解。
$ num[i][j] $ 表示第 $ i $ 至 $ i+5 $ 个围栏，状态为 $ j $ ，会使 $ num[i][j] $ 个小朋友满足，预处理。
我们来看正确性，原有做法是因为不能保证首尾状态相同就死了，我们不妨枚举 \(n\) 的状态 \(i\) ，并将这一状态赋给 $ f[0][i]=0 $ ，由此将其传递给 $ f[1] $ ，这样保证 $ f[1] $ 和 $ f[n] $ 不会冲突。
枚举 \(n\) 的状态时要初始化为无穷小，只给合法的状态赋值，这样经过 $ max $ 后的解一定是合法的。
时间复杂度 $ O(2^{10}\times N) $
Code
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+100;
int n,c,a,b;
int start,f,l,t,fear,like;
int dp[N][1<<6],num[N][1<<6],ans;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%d%d",&n,&c);
for(int i=1;i<=c;i++){
scanf("%d%d%d",&start,&f,&l);
fear=0;
like=0;
for(int j=1;j<=f;j++){
scanf("%d",&t);
t=(t-start+n)%n;//处理环
fear|=(1<<t);
}
for(int j=1;j<=l;j++){
scanf("%d",&t);
t=(t-start+n)%n;
like|=(1<<t);
}
for(int j=0;j<32;j++){
if(((~j)&fear)||(j&like))num[start][j]++;
}
}
for(int i=0;i<32;i++){
memset(dp[0],128,sizeof(dp[0]));//初始化
dp[0][i]=0;//合法状态
for(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])+num[j][k];
}
}
ans=max(ans,dp[n][i]);
}
printf("%d",ans);
}
DP好难，拜谢DP
标签：移走,状压,dp,围栏,动物,高兴,小朋友,APIO,DP From： https://www.cnblogs.com/abnormal123/p/18030233