状压dp
又是一个状压dp题 这个题比较考察思维
So please 拿出一只不同颜色的笔和一个精神饱满的你 准备好脑子
题目大意：
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一 种动物。如下图所示：
你是动物园的公共主管。你要做的是，让每个来动物园的人都尽可能高兴。今天有一群小朋友来动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有的动物有一些小朋友喜欢，有的动物有一些小朋友害怕。如，Alex 喜欢可爱的猴子和考拉，而害怕拥牙齿锋利的狮子。而Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你不能移走所有的动物，否则小朋友们就没有动物可看了。每个小朋友站在大围栏圈的外面，可以看到连续的 5 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：
至少有一个他害怕的动物被移走
至少有一个他喜欢的动物没被移走
例如，考虑下图中的小朋友和动物：
- 假如你将围栏 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,F1,F2……,L1,L2……
其中E表示这个小朋友可以看到的第一个围栏的编号，换句话说，该小朋友可以看到的围栏为E,E+1,E+2,E+3,E+4 。注意，如果编号超过N将继续从1开始算。如：当N = 14 ,E = 13时，这个小朋友可以看到的围栏为 13,14,1,2和3。
F表示该小朋友害怕的动物数。
L表示该小朋友喜欢的动物数。
围栏F1,F2……中包含该小朋友害怕的动物。
围栏L1,L2……中包含该小朋友喜欢的动物。
Fi和Li是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。
小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的E对应的小朋友排在第一个，最大的E对应的小朋友排在最后一个）。
注意可能有多于一个小朋友对应的E是相同的。
输出格式
仅输出一个数，表示最多可以让多少个小朋友高兴。
样例输入
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
样例输出
5
算法分析
状压dp一样按照状压的套路去走
首先先找状态
- 我们定义f数组f[i][j] 其中i表示当前位置为i ，j表示这个时候的移走动物的状态 数组存储当前位置当前状态最多共有多少小朋友会开心
- 显然在当前位置只需要考虑当前位置之后五个地方的状态 用二进制1表示当前位置的动物被移走 0表示不对当前动物进行操作
则动态转移方程很容易就可以出来
f[i][j] = max(f[i-1][(j&15)<<1],f[i-1][(j&15)<<1|1])+num[i][j];
- 那么这个动态转移方程到底是什么意思呢？
首先第一维表示当前位置可以由上一个位置转移过来 i-1即上一个位置 而第二维((j&15)<<1)就是取出当前状态的后四位 如果上一个位置的动物移走的就是((j&15)<<1)|1 如果不移走就是((j&15)<<1) （很显然的问题吧）这两个取较大值 最后再加上当前位置当前状态的小朋友高兴数量 就是转移后的当前的f[i][j]了 - 现在我们来注意细节问题 首先就是当前状态的小朋友高兴数量我们还没有处理 其实这个东西是可以预处理出来的
状态一共就\(2^5\) 也就是32种情况 我们直接枚举就可以 - 那么问题又来了 枚举的时候怎么判断怎样的状态是会使小朋友高兴的呢 这就要用到我们的位运算了
我们已经知道了小朋友不喜欢和喜欢的动物 那我们可以将小朋友喜欢和不喜欢的动物用两个变量记录下来 fear表示不喜欢 love表示喜欢的
如果当前的状态j&fear为真或者~j&love为真 小朋友就会高兴（很有趣的位运算 建议自己推理 并不难）
我们用num[i][j]来记录在i这个位置j这个状态高兴的小盆友数 如果刚才两个判断条件有一个成立 就++num[i][j] - 然后我们来处理环
也很简单 我们用t来记录小朋友喜欢的动物的编号
减去e就是距离他所能看见的第一个动物的距离（为了状态枚举） 最后用+n然后%n的方式处理掉环的问题
t = (t-e+n)%n -
敲黑板
一般来说我们到这里就可以打代码了
但是回忆一个地方
我们的动态转移方程是由上一个状态的后四位转移过来的 而这又是一个环 所以显然n的后四个和1的前四个状态必须一样
如果n的后四个为1111 而 1的前四个是0000 那显然会冲突（要把小动物劈成两半吗？？！震惊），但是我们的代码并不会报错 反而会给出一个更优的值 但这个值是错误的
所以我们需要保证这个n的后四位必须由1前四位相同状态转移过来
所以我们可以把f[0]作为f[n]然后从f[0]的某个状态转移过来
将f的其他状态都设置为一个极小值只有当前状态是0 这样就可以保证其他状态的值绝对不会影响到我们的ans求解 也就能保证f[n]一定是由相同状态的f[1]转移过来的 - 这样我们代码的大体框架就出来了
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4*5;
int f[maxn][40],num[maxn][40],ans;
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i = 1;i <= m;++i){
int e,l,f;
scanf("%d%d%d",&e,&f,&l);
int love = 0,fear = 0,t = 0;
for(int j = 1;j <= f;++j){
scanf("%d",&t);t = (t-e+n)%n;fear |= 1<<t;
}
for(int j = 1;j <= l;++j){
scanf("%d",&t);t = (t-e+n)%n;love |= 1<<t;
}
for(int j = 0;j < 32;++j){
if(((j&fear)||(~j&love)))++num[e][j];
}
}
for(int i = 0;i < 32;++i){
memset(f[0],128,sizeof(f[0]));f[0][i] = 0;
for(int j = 1;j <= n;++j)
for(int s = 0;s < 32;++s)
f[j][s] = max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s];
if(ans < f[n][i])ans = f[n][i];
}
printf("%d\n",ans);
return 0;
}
谢谢观看
点个关注>_<