游客 注册 | 登录
中文 | En

3260 - 动物园

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

绝恋解决问题后成为动物园的VIP*VIP，他帮助的动物园包含一大圈围栏，每个围栏里有一种富有异国风情的动物。如下图所示： 

<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">绝恋准备带着自己的<span>MM</span>们去动物园看动物。他希望能让她们在动物园度过一段美好的时光。但这并不是一件容易的事——有些<span>MM</span>喜欢某些动物，而有些<span>MM</span>则害怕某些动物。例如，<span>Alex </span>喜欢可爱的猴子和考拉，而害怕张牙舞爪的狮子。而<span>Polly</span>会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">绝恋可以选择将一些动物从围栏中移走以使得<span>MM</span>不会害怕。但绝恋移走的动物也不能太多，否则留给<span>MM</span>们观赏的动物就所剩无几了。<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">每个<span>MM</span>站在大围栏圈的外面，可以看到连续的<span>5</span>个围栏。绝恋得到了所有<span>MM</span>喜欢和害怕的动物信息。当出现下面两种情形之一时，<span>MM</span>就会高兴：<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">①至少有一个她害怕的动物（从视线可见的范围内）被移走<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">②至少有一个她喜欢的动物没有被（从视线可见的范围内）移走。<span></span></span>
</p>

例如，考虑下图中的MM和动物： 

<span style="font-size:12.0pt;font-family:宋体;"><img src="http://tk.hustoj.com:80/attached/image/20141018/20141018112853_60911.jpg" alt="" /><br />


<table class="MsoTableGrid" style="border-collapse:collapse;border:none;" border="1" cellpadding="0" cellspacing="0">
	<tbody>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">MM</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">可见的围栏<span></span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">害怕的动物<span></span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">喜欢的动物<span></span></span>
				</p>
			</td>
		</tr>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">Alex</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">2,3,4,5,6</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>4</span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>2,6</span></span>
				</p>
			</td>
		</tr>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">Polly</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">3,4,5,6,7</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>6</span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>4</span></span>
				</p>
			</td>
		</tr>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">Chaitanya</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">6,7,8,9,10</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>9</span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>6,8</span></span>
				</p>
			</td>
		</tr>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">Hwan</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">8,9,10,11,12</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>9</span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>12</span></span>
				</p>
			</td>
		</tr>
		<tr>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">Ka-Shu</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">12,13,14,1,2</span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">围栏<span>12,13, 2</span></span>
				</p>
			</td>
			<td style="border:solid windowtext 1.0pt;" valign="top" width="142">
				<p class="MsoNormal" style="text-align:center;" align="center">
					<span style="font-size:12.0pt;font-family:宋体;">-</span>
				</p>
			</td>
		</tr>
	</tbody>
</table>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">假如绝恋将围栏<span>4</span>和<span>12</span>的动物移走。<span>Alex</span>和<span>Ka-Shu</span>将很高兴，因为至少有一个她们害怕的动物被移走了。这也会使<span>Chaitanya </span>高兴，因为她喜欢的围栏<span>6</span>和<span>8</span>中的动物都保留了。但是，<span>Polly</span>和<span>Hwan</span>将不高兴，因为她们看不到任何她们喜欢的动物，而她们害怕的动物都还在。这种安排方式使得三个<span>MM</span>高兴。<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">现在换一种方法，如果绝恋将围栏<span>4</span>和<span>6</span>中的动物移走，<span>Alex</span>和<span>Polly</span>将很高兴，因为她们害怕的动物被移走了。<span>Chaitanya</span>也会高兴，因为虽然她喜欢的动物<span>6 </span>被移走了，她仍可以看到围栏<span>8</span>里面她喜欢的动物。同样的<span>Hwan</span>也会因可以看到自己喜欢的围栏<span>12</span>里的动物而高兴。唯一不高兴的只有<span>Ka-Shu</span>。<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">如果绝恋只移走围栏<span>13</span>中的动物，<span>Ka-Shu</span>将高兴，因为有一个她害怕的动物被移走。<span>Alex, Polly, Chaitanya </span>和<span>Hwan </span>也会高兴，因为她们都可以看到至少一个她们喜<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;text-indent:24.0pt;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">欢的动物。所以<span>5</span>个<span>MM</span>会高兴。这种方法使得最多的<span>MM</span>高兴。<span></span></span>
</p>

题目输入

输入的第一行包含两个整数N, C，用空格分隔。N是围栏数，C 是MM的个数。围栏按照顺时针的方向编号为1,2,3,…,N。接下来的C 行，每行描述一个MM的信息，以下面的形式给出：

E F L X1 X2 … XF Y1 Y2 … YL

其中：E表示这个MM可以看到的第一个围栏的编号，换句话说，该MM可以看到的围栏为E,E+1,E+2,E+3,E+4。注意，如果编号超过N 将继续从1开始算。如：当N=14, E=13时，这个MM可以看到的围栏为13,14,1,2和3。F表示该MM害怕的动物数。L表示该MM喜欢的动物数。围栏X1,X2,…,XF 中包含该MM害怕的动物。

围栏Y1, Y2, …, YL 中包含该MM喜欢的动物。X1, X2, …, XF, Y1, Y2, …, YL 是两两不同的整数，而且所表示的围栏都是该MM可以看到的。

MM已经按照她们可以看到的第一个围栏的编号从小到大的顺序排好了(这样最小的E对应的MM排在第一个，最大的E对应的MM排在最后一个)。注意可能有多于一个MM对应的E是相同的。 


<p class="MsoNormal" style="text-align:left;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">【数据范围】<span></span></span>
</p>
<p class="MsoNormal" style="text-align:left;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">10</span><span style="font-size:12.0pt;font-family:宋体;">≤<span>N</span>≤<span>10000</span></span>
</p>
<p class="MsoNormal" style="text-align:left;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">1</span><span style="font-size:12.0pt;font-family:宋体;">≤<span>C</span>≤<span>50000</span></span>
</p>
<p class="MsoNormal" style="text-align:left;" align="left">
	<span style="font-size:12.0pt;font-family:宋体;">1</span><span style="font-size:12.0pt;font-family:宋体;">≤<span>E</span>≤<span>N</span></span>
</p>

题目输出

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

输入/输出样例

输入格式

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

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MaxN=100010;
int Hate,Love,N,C,ans=0,E;
int F[MaxN][32]={0},num[MaxN][32];
void DFS(int x,int dep,int status)
{
     if (dep>4)
     {
        if((Love&status)||(Hate&status)!=Hate)num[E][status]++;
        return;
     }
     DFS(x,dep+1,status);
     DFS(x,dep+1,status|(1<<dep));
}
void Init()
{
     int i,H,L,x;
     scanf("%d%d",&N,&C);
     for (i=1;i<=C;i++)
     {
           scanf("%d%d%d",&E,&H,&L);
           Hate=Love=0;
           while (H--){scanf("%d",&x);Hate=Hate|(1<<(x-E+N)%N);}
           while (L--){scanf("%d",&x);Love=Love|(1<<(x-E+N)%N);}
           DFS(i,0,0);
     }
}
int Max(int a,int b){return a>b?a:b;}
void DP(int st)
{
     int i,j,k,r,p,q,w1,w2;
     for (j=0;j<32;j++)F[0][j]=0;
     for (i=1;i<=N;i++)
       if (i<5)
       for (j=0;j<32;j++)
       {
       q=st>>(i-1);
       r=(1<<(5-i))-1;
       if ((j&r)==q)
       {
           w1=(j<<1)&31;w2=w1+1;
           F[i][j]=Max(F[i-1][w1],F[i-1][w2])+num[i][j];
       }
       else F[i][j]=0;
       }
       else if(i+3<N)
       for (j=0;j<32;j++)
       {
           w1=(j<<1)&31;w2=w1+1;
           F[i][j]=Max(F[i-1][w1],F[i-1][w2])+num[i][j];
       }
       else
       {
           q=st&((1<<(i+4-N))-1);
           for (j=0;j<32;j++)
           if ((j>>(N-i+1))==q)
           {
               w1=(j<<1)&31;w2=w1+1;
               F[i][j]=Max(F[i-1][w1],F[i-1][w2])+num[i][j];
           }
           else F[i][j]=0;
       }
     for (j=0;j<32;j++)if(ans<F[N][j])ans=F[N][j];
}
void Solve()
{
     for (int st=0;st<16;st++)DP(st);
     printf("%d\n",ans);
}
int main()
{
    Init();
    Solve();
    return 0;
}
请先登陆