当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

4534:郑厂长系列故事——新闻净化

题目描述
  郑厂长不是正厂长
  也不是副厂长
  他根本就不是厂长
  他曾经是腾讯公司的码农
  一个业余时间喜欢下棋的码农
  但现在
  他神秘失踪了......

  众所周知,在太平洋某岛国,新闻审查是很严格的,而郑厂长的失踪就与该国的新闻审查有关。别担心,他不是喝茶去,而且被秘密邀请承担该国净化新闻的工作了。

  这份工作的主要内容是这样的,对于一篇即将发表的新闻稿,郑厂长需要对它做最后的订正工作:只通过删除一些字母,使其符合“相关要求”。这些要求有,一些词语必须作为子串出现,一些词语必须不能作为子串出现,另一些词语作为子串出现有相应的分数加成,需要注意的是,这个加成分数可能是负的。

  郑厂长要删除最少字母使文章符合要求,并让加成分之和尽可能高。如果一个带有加成分的单词出现了多次,结果也计算多次。
输入解释
输入第一行为T,表示有T组测试数据。
每组数据一个N开始,表示有N个在“相关要求”中的单词。为了简化输入,给每个单词都指定一个加成分,加成分为999的,表示“必须作为子串出现”的,加成分为-999的,表示“必须不能作为子串出现”的。
接下来的N行里,每行有一个单词Si和其对应的加成分Gi。最后一行是原稿内容S_ori。

[Technical Specification]

1. 1 <= T <= 47
2. 1 <= N <= 100
3. -999 <= Gi <= 999
4. Gi 为999的单词数目不大于8
5. Gi 为-999的单词数目不大于8
6. 1 <= |Si| <= 16, 1 <= |S_ori| <= 100, |S| 表示字符串S的长度
7. Si 与 S_ori 只由小写字母 ‘a’-‘z’ 组成,不会出现相同的
输出解释
对每组数据,先输出为第几组数据,如果无法满足要求,输出“Banned”,否则输出两个数字,删除的最少字母和最大分数,用一个空格隔开。
输入样例
3
2
he 999
sh -999
she
2
she 999
he -999
shelovesyou
4
ab 999
cd -999
abd 1
abc -1
abcdefg
输出样例
Case 1: 1 0
Case 2: Banned
Case 3: 1 1

提示
对于第三组样例,”abdefg” 和 ”abcefg” 都符合要求,但前者的加成分比后者高。
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-4534

最后修改于 2020-10-25T23:14:25+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/2000MS(Java/Others) 65535/32768K(Java/Others)