本文共 1592 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要计算小L在选择物品时，使得选出来的总喜欢值大于给定的值M的方案数。每类物品最多只能选择一个物品，可以不选。

方法思路

我们可以使用动态规划的方法来解决这个问题。具体步骤如下：

这种方法通过逐层处理每个层级，并记录当前的总和，避免了重复计算，并且在处理v超过M的情况时，可以立即计入结果，从而减少计算量。

解决代码

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    while ptr < len(input):
        k = int(input[ptr])
        M = int(input[ptr+1])
        ptr +=2
        layers = []
        for _ in range(k):
            ai = int(input[ptr])
            vs = list(map(int, input[ptr+1:ptr+1+ai]))
            layers.append(vs)
            ptr += 1 + ai
        result = 0
        dp_current = {0:1}
        for vs in layers:
            dp_next = {}
            for v, count in dp_current.items():
                for vj in vs:
                    new_v = v + vj
                    if new_v > M:
                        result += count
                    else:
                        if new_v in dp_next:
                            dp_next[new_v] += count
                        else:
                            dp_next[new_v] = count
            dp_current = dp_next
        print(result)
if __name__ == "__main__":
    main()

代码解释

这种方法有效地计算了满足条件的方案数，避免了重复计算，并且在处理较大值时表现良好。

转载地址：http://znrq.baihongyu.com/