atcoder abc142 E题Get Everything 题解

atcoder abc142 E题Get Everything 题解

终于把ABCD全做出来,可以挑战到E题了

题意:

有N个宝箱,标记序号为1到N。商店中有M把钥匙在销售。第i把钥匙售价ai,它能开的宝箱子有bi个,分别是ci,1,ci,2,…ci,bi,现希望将所有N个箱子都打开,试求买钥匙的最小花费。若不可能打开所有宝箱,则输出-1。数据范围:N不超过12,M不超过1000

分析:

不难看出,钥匙可打开的箱子可以用比特位数据节省空间和运算量:钥匙能打开第k(范围从1到N)个箱子,就把这个钥匙的标志位第k-1位二进制上置为1。如果多把钥匙的标志位进行按位或运算结果是二进制N位的1说明这些钥匙可以开启全部宝箱。

用动态规划解可以达到O(M*2^N)的时间复杂度,由于N最大只有12所以运算量还算合理。主要方法是:用dp[signs]记下开signs(sign二进制第k位为1表示第k个宝箱能开)宝箱的最小花费,初始整个列表为一个极大的整数,同时dp[0]=0,表示不开箱时花费为0

对于每一把钥匙,更新它所指的能开的signs所对的最小花费。所有钥匙都更新完成之后,检查dp[(1<<N)-1]是否为初始的极大整数,若是说明没有钥匙能打开所有宝箱,此时输出-1,否则输出 dp[(1<<N)-1] 的值


class _const:
    def __init__(self):
        self.__INT_MAX = 0x7fffffff

    @property
    def INT_MAX(self):
        return self.__INT_MAX

const=_const()

N,M=map(int,input().split(" "))
dp=[ const.INT_MAX for i in range((1<<N)) ]
dp[0]=0
for i in range(M):
    val,T=map(int,input().split(" "))
    r=list( map(int,input().split(" ")) )
    
    now = 0
    for it in r:
        now |= (1<<(it-1))
    for bits in range((1<<N)):
        dp[bits | now] = min(dp[ bits | now ],dp[bits]+val)


if dp[-1]==const.INT_MAX:
    print("-1")
else:
    print(dp[-1])

发表评论

电子邮件地址不会被公开。 必填项已用*标注