极客杯-快乐假期-GGboy分饺子

先看问题是什么：

每个孩子分到的饺子数目的最大值的最小值，有点绕

其实就是说，分配的方案有很多种，每一种方案都有一个孩子分到的饺子数目是最多的，这个值我们设为。现在的目标是求这个的最小值。

状态定义：

状态转移：

考虑给第给孩子分配的饺子集合为，设集合对应的饺子数目为

分类讨论：

如果cnt[s]>f(i-1, j^s), 说明第i个孩子分的饺子数目比之前的多，那么就要变为cnt[s]，因为第i个孩子分到的饺子数目比之前的孩子都多。那第i个孩子分到的饺子数目就是最多的，因此更新

否则，不变

枚举 j 的所有子集 s，则有

代码实现时，我们可以用一个二进制数来表示集合，其第 i 位为 1 表示分配了第 i 包饺子，为 0表示未分配第 i 包饺子。

具体实现我这里采用记忆化搜索

def I(): return input()


def II(): return int(input())


def MI(): return map(int, input().split())


def LI(): return list(input().split())


def LII(): return list(map(int, input().split()))

n, k = MI()

arr = LII()

# 预处理每个孩子可以分配到的饺子情况，因为最多11包饺子，用二进制表示也才2^11种
m = 1 << n 
state = [0]*m # state[i]：i这种情形，分到了多少个饺子

for i in range(m):
    t = 0
    for j in range(n):
        if (i >> j) & 1:
            t += arr[j]
    state[i] = t 


from functools import lru_cache

@lru_cache(None)
def solve(k, mask):
    # mask是已经分配的饺子
    if k == 0:
        # 所有的孩子都分配完了，判断下饺子是否分配完毕
        if mask == m-1:
            return 0
        return float("inf") 
    tot = (m-1)^mask # tot是还没分配的饺子
    s = tot # s是tot的子集
    ans = float("inf")
    while s != 0:
        ans = min(ans, max(solve(k-1, s|mask), state[s]))
        s = (s-1)&tot 
    return ans 

res = solve(k, 0)
print(res)