- GRE Words 单词的程序设计
Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words.
Now George is working on a word list containing N words.
He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember.
So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn't want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word.
Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence.
The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 2 * 104), indicating the number of words.
Then N lines follows, each contains a string Si and an integer Wi, representing the word and its importance. Si contains only lowercase letters.
You can assume that the total length of all words will not exceeded 3 * 105.
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is the largest importance of the remaining sequence of words.
Case #1: 14
- 博客 大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 技术大佬：我去，你写的 switch 语句也太老土了吧
- 博客 上班一个月，后悔当初着急入职的选择了
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 程序员写出这样的代码，能不挨骂吗？
- 博客 我说我不会算法，阿里把我挂了。
- 博客 带了6个月的徒弟当了面试官，而身为高级工程师的我天天修Bug......
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 C语言的灵魂之指针
- 博客 为什么程序员做外包会被瞧不起？
- 博客 10个提升效率的编程好习惯
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发
- 博客 《Java经典编程365例》000：学妹的优秀成绩单
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 Python爬虫，高清美图我全都要（彼岸桌面壁纸）
- 博客 无代码时代来临，程序员如何保住饭碗？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 6年开发经验女程序员，面试京东Java岗要求薪资28K
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 Java岗开发3年，公司临时抽查算法，离职后这几题我记一辈子
- 博客 都前后端分离了，咱就别做页面跳转了！统统 JSON 交互
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 程序员是做全栈工程师好？还是专注一个领域好？