题目描述
f1-记忆化搜索+轮廓线状态压缩 |
基本分析
- 轮廓线状态压缩的场景?在一个二维矩阵上进行动态规划+数据规模不大+可以通过当前位置与其左上方位置+左侧位置计算转移方程
- 为什么存n个状态而不是相关的2个状态?只存2个会丢状态,新的0找不到了;存n个可以递推出
- 具体怎么计算得分?新加人产生的分可分为:填进去的人的分+上侧相邻导致的贡献+左侧相邻导致的贡献;规定贡献的计算方法是下侧和右侧计算,这样可以按照行优先的顺序枚举位置,进行状态转移
- 在dp前进行哪些预处理?
- (1)对每个状态mask,存他对应的0-n-1的每一位值。这里的要求是最高位对应0,最低位对应n-1
- (2)对每个mask,存截断第0位,同时再末尾分别追加0,1,2后的值
- dp时候有哪些细节?
- (1)有可能计算出的pos位置在第一列,这个时候不存在左侧影响,对应的add_l是0
- (2)有可能计算出的pos位置在第一行,这个时候不存在上侧影响,可以假设存在虚拟的第0行,该行状态都是0
- dfs怎么写?
- dfs参数:位置pos,当前轮廓线bl,剩余内向ni,剩余外向nx
- 结束条件:位置达到边界或者人分配完,都可以结束返回0
- 枚举情况:
- (1)pos处不放人,这个时候可以拿到不放对应的best值
- (2)放内向的人,取max(best,内向人得分 + 上侧影响 + 左侧影响 + 后续情况)
- (3) 放外向的人,取max(best,外向人得分 + 上侧影响 + 左侧影响 + 后续情况)
- 返回情况:返回当前状态结果best
代码
class Solution:
def getMaxGridHappiness(self, m: int, n: int, ni: int, ne: int) -> int:
def calc(x, y):
if x==0 or y==0:
return 0
if x==1 and y==1:
return -60
if x==2 and y==2:
return 40
return -10
n3 = 3**n
high = n3//3
# 存数字对应的3进制
mask_span = dict()
# 存数字截断高位,低位+0,1,2后的值
truncate = dict()
for mask in range(n3):
mask_temp = mask
bits = list()
for i in range(n):
bits.append(mask_temp % 3)
mask_temp //= 3
mask_span[mask] = bits[::-1]
truncate[mask] = [mask % high * 3, mask % high * 3+1, mask % high * 3+2]
@lru_cache(None)
def dfs(pos, bl, ni, ne):
if pos == m*n or ni+ne==0:
return 0
x, y = divmod(pos, n)
# 不放
best = dfs(pos+1, truncate[bl][0], ni, ne)
# 放1-内向
if ni > 0:
add_t = calc(1, mask_span[bl][0])
add_l = calc(1, mask_span[bl][n-1]) if y > 0 else 0
best = max(best, 120 + add_t + add_l + dfs(pos+1, truncate[bl][1], ni-1, ne))
# 放2-外向
if ne > 0:
add_t = calc(2, mask_span[bl][0])
add_l = calc(2, mask_span[bl][n-1]) if y > 0 else 0
best = max(best, 40 + add_t + add_l + dfs(pos+1, truncate[bl][2], ni, ne-1))
return best
return dfs(0, 0, ni, ne)
复杂度
时间:
- \(预处理部分计算mask的3进制表示以及mask0, mask1, mask2的复杂度是O(n\cdot 3^n)\)
- \(记忆化搜索部分状态总数是O(m \cdot n \cdot ni\cdot ne \cdot 3^n), 转移需要枚举3=O(1)个状态,转移时间复杂度是O(1)\)
空间: - \(预处理mask的3进制表示是O(n*3^n)\)
- \(预处理mask的截断操作是O(3^n)\)
- \(记忆化搜索的空间为状态总数O(m \cdot n \cdot ni\cdot ne \cdot 3^n)\)
总结
这是第一次碰到轮廓线dp的题。
和之前的相比,(1)选择多了,不再是选和不选,而是有3种可能;(2)用3进制表达相比二进制,没有位运算那么方便了,这里需要预处理mask的3进制每一位的表达;也需要预处理转移后状态的表达;(3)写转移的时候因为是在记忆化搜索里面,所以可以把后面结果当做已知,反而会比较简单。
遇到当前选择会影响之前值的情况,这里是定义了一个规则(由下和右)的位置进行补偿,只要考虑怎么计算这个值。