* 绿题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意:
* 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代码:
时间复杂度:O(N + M)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
由AI润色,写的不好勿喷
求赞φ(>ω<*) ,完结撒花ヾ(。∀。ゞ)