首页 > 其他分享 >动物园

动物园

时间:2024-04-08 15:56:24浏览次数:19  
标签:移走 样例 le 围栏 动物 小朋友 动物园

[APIO2007] 动物园

题目描述

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

你是动物园的公共主管。你要做的是,让每个来动物园的人都尽可能高兴。今天有一群小朋友来动物园参观,你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有的动物有一些小朋友喜欢,有的动物有一些小朋友害怕。如,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\) 是围栏数(\(10 \le N \le 10^4\)),\(C\) 是小朋友的个数(\(1 \le C \le 5\times 10^4\))。

围栏按照顺时针的方向编号为 \(1,2,3,\cdots,N\)。

接下来的 \(C\) 行,每行描述一个小朋友的信息,以下面的形式给出: \(E, F, L ,X_1, X_2 ,\cdots ,X_F ,Y_1 ,Y_2 ,\cdots ,Y_L\)。

其中: \(E\) 表示这个小朋友可以看到的第一个围栏的编号(\(1 \le E \le N\)),换句话说,该小朋友可以看到的围栏为 \(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\) 是相同的。

输出格式

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

样例 #1

样例输入 #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

样例 #2

样例输入 #2

12 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

6

提示

数据范围
对于 \(100\%\) 的数据,\(10 \le N \le 10^4\),\(1 \le C \le 5\times 10^4\),\(1 \le E \le N\)。

样例说明

  • 第一个样例是题目描述中的例子,所有的 \(C=5\) 个小朋友都能高兴。
  • 第二个样例是一个不能使得所有 \(C=7\) 个小朋友都高兴的例子。

从数据范围可知,直接状态压缩不太可能
所以我们只能对每一个小朋友的视野范围内的栅栏状态压缩
我们初步有了一个思路\(F[i,j]i表示第几个围栏,j表示状态,因为当前小朋友的栅栏只与旁边的小朋友看到的栅栏有关\)
首先预处理时考虑到可能小朋友看见的围栏范围可能相同,那么我们可以预处理num[pos][s],表示从第pos个围栏开始的五个围栏状态为s时,会有多少个小朋友满意。
然后动态转移方程

\[F[j,k]=max(f[j-1][(k\And 15)<<1],f[j-1][(k\And 15)<<1|1])+num[j][k] \]

15二进制下为00001111
所以表示从上一个栅栏转移到当前栅栏
可以由第j-1个围栏移走和不移走两种状态转移得来
因为围栏是一个环,最后枚举第n+1个围栏时,其实就相当于又回到了第一个围栏,那么此时必须满足s=state才是有效状态,更新答案。

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N =5e4+10;
int n,c,E[N];
int f[N][(1<<6)+5];
int num[N][40];
//vector <int> like[N],dis[N];
int main()
{
	scanf("%d%d",&n,&c);
	int F,l;
	for(int i=1;i<=c;i++)
	{
		int like=0,dis=0;
		scanf("%d%d%d",&E[i],&F,&l);
		for(int j=1;j<=F;j++)
		{
			int a;
			scanf("%d",&a);
			a=(a-E[i]+n)%n+1;
			like|=1<<(a-1);
		}
		for(int j=1;j<=l;j++)
		{
			int a;
			scanf("%d",&a);
			a=(a-E[i]+n)%n+1;
			dis|=1<<(a-1);
		}
		for(int j=0;j<(1<<5);j++)
		{
			if((j&like)||(~j&dis))
			{
				num[E[i]][j]++;
			}
		}
	}
	int ans=INT_MIN;
//	cout<<ans;
	for(int i=0;i<(1<<5);i++)
	{
		memset(f[0],128,sizeof(f[0]));
		f[0][i]=0;
		for(int j=1;j<=n;j++)
		{
			for(int k=0;k<(1<<5);k++)
			{
				f[j][k]=max(f[j-1][(k&15)<<1],f[j-1][(k&15)<<1|1])+num[j][k];
			}
		}
		if(ans<f[n][i])ans=f[n][i];
	}
	cout<<ans;
	return 0;
}

标签:移走,样例,le,围栏,动物,小朋友,动物园
From: https://www.cnblogs.com/wlesq/p/18121317

相关文章

  • P3622 [APIO2007] 动物园 -题解
    好写爱写没事干所以有了这篇题解洛谷P3622[APIO2007]动物园题解$Link$hzoi题库洛谷题目说的挺繁琐,其实就传达了一个很简单的信息:\(n\)个动物,\(c\)个小孩,每个小孩能看到\(5\)个动物(所在的位置)\(E\)到\(E+4\),有\(F\)个害怕的动物,\(L\)个喜欢的动物。如果视野中有至......
  • 动物园 (APIO 2007) 状压DP
    动物园\([APIO\2007]\)·题意:新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望能让他......
  • 动物园(APIO 2007)(状压DP)
    动物园题解题目描述原题来自:APIO2007新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望......
  • 多平台互通《因果动物园》支持PC、主机、Switch的欢乐合作ibb游戏
    DevolverDigital与游戏开发团队Pastagames合作,共同推出了一款名为《因果动物园》(KarmaZoo)的合作游戏。这是一款欢乐且支持多达十名玩家同时游玩的ibbgames游戏,而且有一非常特别的特点,那就是它的游戏通.行.证是完全免.费的。《因果动物园》强调合作、互助和寻求共赢。你可以与最多......
  • 10.11(动物园管理员)
    第一版:把每种动物都定义为一个类,漏洞大,每天加一种动物或者动物数量发生变化都会需要对代码进行调整每种动物的喂食函数名也不同packagehomework;publicclasstext{publicstaticvoidmain(Stringargs[]){Feederf=newFeeder("小王");......
  • 动物园
    Smiling&Weeping----你是我的,半截的诗,不许别人更改一个字 题目链接:P2375[NOI2014]动物园-洛谷|计算机科学教育新生态(luogu.com.cn)思路详解:这道题目是要求解:有多少个我现在希望求出一个更强大 num 数组一一对于字符串 S 的前......
  • 大熊猫直播还没有看?TSINGEE轻松打造动物园直播方案,在线看,时时看~
    最近旅居韩国的大熊猫爱宝喜添双胞胎,新闻迅速登上了热搜。不仅爱宝、乐宝、福宝,国内萌萌的花花、阳光开朗大男孩西直门三太子萌兰等也长期霸占各大平台的热搜词条。在成都大熊猫繁育研究基地,络绎不绝的游客们为了一睹“顶流女明星”花花的芳容,不惜排队半天。根据公开资料显示,顶流......
  • 【题解】 [APIO2007] 动物园
    目录题目链接原题描述题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示题意概括思路历程1.与环相关2.设计状态代码实现题目链接原题描述[APIO2007]动物园题目描述新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个......
  • Luogu P2375 [NOI2014] 动物园
    [NOI2014]动物园题目描述近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。某天,园长给动物们讲解KMP算法。园长:“对于一个字符串\(S\),它......
  • [NOI2014]动物园
    [NOI2014]动物园这题看题目描述就知道一定是跟KMP扯上关系了。首先,如果不考虑长度超过\(\dfrac{1}{2}\)的限制的话,那么就很简单,每次求出一个新的\(ne_i\)时,如下图所示图中红色的表示目前对于前\(i\)个字符来说,最长公共前后缀为红色部分,因为两个红色部分中一定都有前后......