c/c++语言开发共享题解 洛谷P3622/BZOJ1151【[APIO2007]动物园】

这一道题,我也是搞了很久才搞懂的(也就两个多小时)。

感谢rayment大佬的题解!

我们进入正题。

对于一个笼子里的动物,我们可以选择撤走或不撤走,可以用0和1来表示,很容易就想到二进制,想到状压dp(为什么先选dp,看数据想想吧)。

观察题面,我们可以发现,小朋友最多可达五万人(动物园容得下吗…)!太大了,肯定不能来做状压dp。

不过,正当我们努力寻找更小的可以用来状压dp变量时,去忽略了题面上的一点:

每个小朋友站在大围栏圈的外面，可以看到连续的 5 个围栏

5,这个数字很小,可以用来状压!

所以,我们可以列出状态转移方程:

f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s];

(f[i][s]表示{i,i+1,i+2,i+3,i+4}这五个围栏状态为s时,开心的小朋友数)

可能看不懂,我们来剖析一下这个状态转移方程

首先,为什么这里是 &15 ,而不是其他的变量呢?

转换成二进制,我们惊奇的发现:

                 15(10)=01111(2)

15的用处就出来了:取后四位

继续来看:

         |-------------------------------|              |第几个围栏:|7 |6 |5 |4 |3 |2 |1 |          |----------|--|--|--|--|--|--|--|          |此围栏状态:|0 |1 |0 |1 |0 |0 |1 |          |----------|--|--|--|--|--|--|--|          |当前i    :|1 |1 |1 |1 |1 |     |          |-------------------------------|

i开始的状态是10100,对应的是{3,4,5,6,7}。状态的后四位是0100,我们要考虑的就是i-1开始的前四位是0100的最优状态。

所以考虑是在0100后面放0还是1(有五个围栏)

在后面放,理所当然,i-1看到了{2,3,4,5,6}。可用来转移。

最后一点:num[i][s]为已经预处理出来的数组,它的意思为:

i,i+1,i+2,i+3,i+4 几个围栏的状态为s是开心的小朋友数

• 关于num的预处理

上文已经提到,num是预处理出来的数组,那么怎么来预处理呢?
我们先来看代码:

scanf("%d%d",&n,&m); for(register int i=1;i<=m;++i) {    int a,b,c,t,like=0,fear=0;     scanf("%d%d%d",&a,&b,&c);     for(register int j=1;j<=b;++j)    {scanf("%d",&t);t=(t-a+n)%n;fear|=1<<t;}    //l表示这五个围栏中这个小朋友害怕的动物的状态     for(register int j=1;j<=c;++j)    {scanf("%d",&t);t=(t-a+n)%n;like|=1<<t;}     //like表示这五个围栏中这个小朋友喜欢的动物的状态     for(register int j=0;j<32;++j)      if(((j&fear)||(~j&like)))++num[a][j];  }

来慢慢解释:

先看这一句:

      scanf("%d",&t);t=(t-a+n)%n;fear|=1<<t;

我们来看看过程(就以第一个样例中的最后一个小朋友当例子)：

   ka-shu可以看到的围栏:{12,13,14,1,2}    起初,fear是等于0的:     fear： 0(10)    00000(2)    然后,读入了12,12是ka-shu可以看到的所有围栏中的第一个    于是:    1<<(1-1)=1;1(10)=00001(2)    fear: 0|1=1(10)    00001(2)    读入13,是第二个。    于是:    1<<(2-1)=2;2(10)=00010(2)    fear: 1|2=3(10)    00011(2)    读入2,是第五个。    于是:    1<<((5-1)=32;32(10)=10000(2)    fear: 3|32=35(10)  10011(2)    所以,我们得到了状态:10011(2),35(10)

读取like状态的那一句同上。

再看这一句:

             if(((j&fear)||(~j&like)))

j的每一个二进制位上的 0/1 表示 没撤走/撤走。

再看题目:

• 至少有一个他害怕的动物被移走

• 至少有一个他喜欢的动物没被移走

  联系一下上面的if,是不是想通了?

dp可以愉快的开始了!

memset(f[0],128,sizeof(f[0]));//预处理为极小数 f[0][i]=0; for(register int j=1;j<=n;++j)//枚举每一行    for(register 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];

综合以上,我们基本上各方面都搞懂了,接下来,只剩下拼在一起了

ac代码:

#include<bits/stdc++.h> #define ll long long using namespace std; const int n=50010; int n,m,ans,f[n][40],num[n][40]; void input() {     scanf("%d%d",&n,&m);     for(register int i=1;i<=m;++i)     {         int a,b,c,t,like=0,fear=0;          scanf("%d%d%d",&a,&b,&c);          for(register int j=1;j<=b;++j)         {scanf("%d",&t);t=(t-a+n)%n;fear|=1<<t;}         //l表示这五个围栏中这个小朋友害怕的动物的状态          for(register int j=1;j<=c;++j)         {scanf("%d",&t);t=(t-a+n)%n;like|=1<<t;}          //like表示这五个围栏中这个小朋友喜欢的动物的状态          for(register int j=0;j<32;++j)           if(((j&fear)||(~j&like)))++num[a][j];      }return; } int main() {     input();     for(register int i=0;i<32;++i)     {         memset(f[0],128,sizeof(f[0]));f[0][i]=0;         for(register int j=1;j<=n;++j)//枚举每一行            for(register 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("%dn",ans);     return 0; }