# coding=utf-8 import sys def f2(a, types): n = len(a) max_card = -1 for i in range(len(a)): # 这里可以优化 node = [int(e) for e in str(a[i])] max_card = max(max_card, max(node)) node = set(node) t = 0 for e in node: e = int(e) t += ((2**(e))) a[i] = t b = [bin(i)[2:] for i in a] if max_card < types: return -1 max_len = [len(b_node) for b_node in b] size = 2 ** max(max_len) dp = [[float('inf') for i in range(size)] for _ in range(n)] item0 = a[0] for j in range(size): dp[0][j] = 1 if j == item0 else float('inf') for i in range(n): dp[i][0] = 0 for i in range(1,n): item = a[i] for j in range(size): new_j = j | item dp[i][new_j] = min(dp[i][new_j], dp[i-1][j]+1, dp[i][new_j]) dp[i][j] = min(dp[i-1][j], dp[i][j]) return dp[-1][-2] t = input() for i in range(t): mnk = sys.stdin.readline().split() n,m,k = int(mnk[0]), int(mnk[1]), int(mnk[2]) items = [] for nn in range(n): cards = sys.stdin.readline().split() items.append(int("".join(cards))) print(f2(items, m))典型的0-1背包问题,dp[i][j]: 前i个商品,能收集到j张卡牌的最小商品数量, 注意这里的j必须能记录特定的卡牌是否已经放进背包,一共也就10张卡牌,所以可以用二进制的每一位表示一张卡牌,比如商品内有卡牌'420', 那么他的体积就是1011,其中1的位置就代表了对应的卡
## 注意这里我是针对字节的题目的分析,字节机考略有不同
全部评论
(0) 回帖