题解

• 绿题

---

题目大意：

• 1.动物园有 n 个围栏（环形排列），m 个小朋友

• 2.每个小朋友能看到连续的 5 个围栏（以位置 o 为起点）

• 3.每个小朋友有害怕的动物（p 个）和喜欢的动物（q 个）

• 4.小朋友高兴的条件：至少一个害怕的动物被移走，或至少一个喜欢的动物保留

解决方法：

• 1.用 5 位二进制数（0-31）表示连续 5 个围栏的动物是否被移走（1 表示移走，0 表示保留）

• 2.定义 bool 数组f[o][j]：处理到第 i 个围栏时，以 i 为起点的连续 5 个围栏状态为 s 时，能让最多多少小朋友高兴

解题思路：

• 1.写出状态转移方程：dp[i][s]=max(dp[i−1][(s & 15)≪1], dp[i−1][((s & 15)≪1) ∣ 1])+f[i][s]

• 2.模拟

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,b[1000],a[1005],f[10015][35],cnt,nm[1000],dp[10010][35],ans=0;
int main(){
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int o,p,q,t1=0,t2=0;
		cin>>o>>p>>q;
		for(int j=1;j<=p;j++){
			int x;
			cin>>x;
			t1|=(1<<((x-o+n)%n));
		}
		for(int j=1;j<=q;j++){
			int x;
			cin>>x;
			t2|=(1<<((x-o+n)%n));
		}
		for(int j=0;j<32;j++){
			if(((~j)&t1)||(j&t2)){
				f[o][j]++;
			}
		}
	}
	for(int i=0;i<32;i++){
	    memset(dp,-0x3f,sizeof(dp));
	     dp[0][i]=0;
		for(int j=1;j<=n;j++){
			for(int k=0;k<32;k++){
				dp[j][k]=max(dp[j-1][((k&15)<<1)],dp[j-1][((k&15)<<1)|1])+f[j][k];
			}
		}
		ans=max(ans,dp[n][i]);
	}
    cout<<ans;
	return 0;
}

时间复杂度：O(n + m)

---

由AI润色，写的不好勿喷

求赞φ(>ω<*) ，完结撒花ヾ(。∀。ゞ)