摘要
Title: 1243. 糖果
Tag: 状压dp、重复覆盖问题
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1243. 糖果

• 题意

  糖果店的老板一共有 M 种口味的糖果出售。
  为了方便描述，我们将 M 种口味编号 1∼M。
  小明希望能品尝到所有口味的糖果。
  遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。
  幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
  给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

• 思路

  重复覆盖问题：最少选几行，使得每一列均至少存在一个1
  解决方法：

  • dancing links
  • 状压dp
  • 爆搜
    • 迭代加深
    • 找选择最少的列
    • 可行性剪枝

  此处为了代码简短和易理解，采用状压dp来做
  

  推出了二维式子，但其实发现，对于第一维$i$只会用到$i-1$的数据，也就是可以采用优化01背包的策略，将数组优化成一维

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-02 14:07:41
  FilePath: \ACM\Acwing\1243.py
  LastEditTime: 2022-04-02 14:14:11
  '''
  N = 110
  INF = int(1e18)
  lst = []
  a = [0] * N
  f = [INF] * (1 << 21)
  
  n, m, k = map(int, input().split())
  for i in range(n):
      b = list(map(int, input().split()))
      for j in b:
          a[i] |= 1 << (j - 1)
  
  f[0] = 0
  for i in range(n):
      for j in range(1 << m):
          f[j] = min(f[j], f[j & (~a[i])] + 1)
  
  if f[(1 << m) - 1] > n:
      print(-1)
  else:
      print(f[(1 << m) - 1])