[APIO2007] zoo problem solving record

Title: https://www.luogu.org/problemnew/show/P3622

Reference questions: https://qiu.blog.luogu.org/solution-p3622

At the beginning of this question, I considered each child as the stage of dp, and later found that it was difficult to avoid the conflict before and after, only 45 points.

45 point code:

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio> 
 5 #include<cmath>
 6 using namespace std;
 7 const int N=10000;
 8 const int M=31+7;
 9 const int C=50000+7;
10 void pre(int,int*);
11 void init();
12 bool check(int,int,int);
13 void run();
14 int ans,lim=1<<5;
15 int main(){
16     init();
17     printf("%d\n",ans);
18     return 0;
19 }
20 int n,c,st[C],h[C],l[C],s[7],ext;
21 void init(){
22     cin>>n>>c;
23     int h,l,x;
24     for(int i=1;i<=c;i++){
25         memset(s,0,sizeof(s));
26         scanf("%d%d%d",&st[i],&h,&l);
27         for(int j=1;j<=h;j++){
28             scanf("%d",&x);
29             x= x<st[i] ?x+n :x;
30             s[x-st[i]+1]=1;
31         }
32         for(int j=1;j<=l;j++){
33             scanf("%d",&x);
34             x= x<st[i] ?x+n :x;
35             s[x-st[i]+1]=2;
36         }
37         pre(i,s);
38     }
39     int tail=st[c]+5-1-n;
40     if(tail>0)
41         while(tail>=st[ext+1])
42             ext++;
43 }
44 int f[C][M],dp[C][M];
45 bool zero[C][M];
46 void pre(int u,int *s){
47     for(int i=0;i<lim;i++){
48         int t=i,cnt=0;
49         for(int j=1;j<=5;j++){
50             if(s[++cnt]==(t&1)+1){
51                 f[u][i]=1;
52                 if(u==1)dp[u][i]=1;
53                 break;
54             }
55             t>>=1;
56         }
57     }
58 }
59 void run(){
60     for(int j=0;j<lim;j++)
61         zero[1][j]=1;
62     for(int i=2;i<=c+ext;i++){
63         int l,r,step;
64         if(i>c){
65             memset(dp[i],0,sizeof(dp[i]));
66             memset(zero[i],0,sizeof(zero[i]));
67             l=i==c+1 ?c :i-1-c;
68             r=i-c;
69         }
70         else l=i-1,r=i;
71         if(i==c+1) step=st[l]+5-(st[r]+n);
72         else step=st[l]+5-st[r];
73         step=max(step,0);
74         for(int j=0;j<lim;j++){
75             if(i>c) dp[r][j]=0;
76             for(int k=0;k<lim;k++)
77                 if(check(j,k,step)&&dp[l][k]>=dp[r][j]){
78                     dp[r][j]=dp[l][k];
79                     zero[r][j]=(zero[l][k]&&j==0);
80                 }
81             if(f[r][j]) dp[r][j]++;
82         }
83     }
84     if(ext)c=ext;
85     for(int i=0;i<lim;i++)
86         if(!zero[c][i]) ans=max(ans,dp[c][i]-ext);
87 }
88 bool check(int a,int b,int step){
89     if(step==0)return 1;
90     a&=(int)pow(2,step)-1;
91     b>>=5-step;
92     if(a==b)return 1;
93     else return 0;
94 }

Later, I looked at the solution and found that each fence should be taken as the stage of dp. The general idea is as follows:

1. Read in and preprocess out num[i][j] (the number of happy children when the last 5 bits are j from I)

2. dp, the transfer equation is as follows. PS. dp here needs to be carried out many times (2 ^ 5 times). When i = n is determined first, the state of the last 5 bits is set to t, and only the value of dp[n][t] is taken at the end, so as to ensure that there is no conflict between before and after.

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

AC code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 using namespace std;
 6 const int N=10000+7;
 7 const int M=32+7;
 8 void init();
 9 void run();
10 int ans;
11 int main(){
12     //freopen("1.txt","r",stdin);
13     init();
14     run();
15     printf("%d\n",ans);
16     return 0;
17 }
18 int n,c,lim=32,st,a,l,x,afraid,love,num[N][M];
19 void init(){
20     cin>>n>>c;
21     for(int i=1;i<=c;i++){
22         scanf("%d%d%d",&st,&a,&l);
23         afraid=love=0;
24         for(int j=1;j<=a;j++){
25             scanf("%d",&x);
26             int t=(x-st+n)%n;
27             afraid|=1<<t;
28         }
29         for(int j=1;j<=l;j++){
30             scanf("%d",&x);
31             int t=(x-st+n)%n;
32             love|=1<<t;
33         }
34         for(int j=0;j<lim;j++){
35             if(~j&afraid || j&love) num[st][j]++;
36         }
37     }
38 }
39 int dp[N][M];
40 void run(){
41     for(int t=0;t<lim;t++){
42         memset(dp,128,sizeof(dp));
43         dp[0][t]=0;                    // It is equivalent to determining the last position first, so as to avoid conflict. 
44         for(int i=1;i<=n;i++)
45             for(int j=0;j<lim;j++)
46                 dp[i][j]=max(dp[i-1][(j&15)<<1],dp[i-1][(j&15)<<1|1])+num[i][j];
47         ans=max(ans,dp[n][t]);
48     }
49 }

Tucao, this question clearly says "can't remove all animals", but the answer seems not to have been judged.

Tags: PHP

Posted on Fri, 01 Nov 2019 12:00:26 -0700 by teng84