2022.11.26 美团笔试 祝福血怒_美团笔试 血怒 祝福

笔试时用的 dfs 加普通剪枝 55%（贪心只能过 36%），笔试后琢磨了下动态规划，解出来了，妈的，思路变一下，简单的要死，这应该算背包九讲里的泛化背包问题了。

令 mem[j] 为 i 价值时存储的最大攻击力数值，每个卡牌遍历更新一遍 mem。复杂度 $O(N^2)$

def solve2(m):
    n = len(m)
    mem = defaultdict(int)
    mem[0] = 1
    
    ans = 0
    for i in range(n):
        for k, v in list(mem.items()):
            if m[i] == 0:
                mem[k + v] = max(mem[k + v], v)
                ans = max(k + v, ans)
            else:
                mem[k // 2] = max(mem[k // 2], v + 1)
                # mem[k // 2] = max(mem[k // 2], v + 1)
    return ans
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16