#Pold1261. 算法训练 Buying Sets

    ID: 578 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>蓝桥杯-算法训练赛制:ACM来源:蓝桥杯练习系统 ID: 355 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T355状压DP

算法训练 Buying Sets

算法训练 Buying Sets

题目描述

给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目.   对于任意的k(1<=k<=n), 满从中选出任意k个集合, 这k个集合的并集的势一定大于等于k.   每个集合有一个权值, 每个选择方案的代价是所选的集合的权值的和.   请输出代价最小的选择方案的代价.   当然, 不选择任何一个集合是一个可行的方案(权值和为0), 但不一定最优(权值和可以为负).

输入格式

输入描述:   第一行一个正整数n(1<=n<=300), 为集合个数.   在接下来n行中, 第i行描述第i个集合:   首先给出一个正整数m[i]为该集合的势, 显然1<=m[i]<=n.   接下来m[i]个在1到n之间的整数, 表示该集合中的元素.   最后一行n个整数, 为每个集合的权值, 绝对值不超过1e6. 输入样例: 3 1 1 2 2 3 1 3 10 20 -3

输出格式

输出描述:   仅一个整数, 为代价最小的选择方案的代价. 输出样例: -3

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:2.0s 内存限制:256.0MB