动态规划算法
1. Max Sum
1. 最大总和
Problem Description
问题描述
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
给定序列 a[1]，a[2]，a[3]......a[n]，你的工作是计算子序列的最大和。例如，给定 （6，-1,5,4，-7），此序列中的最大总和为 6 + （-1） + 5 + 4 = 14。
Input
输入
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
输入的第一行包含一个整数 T（1<=T<=20），表示测试用例的数量。然后是 T 行，每行以一个数字 N（1<=N<=100000） 开头，然后是 N 个整数（所有整数都在 -1000 和 1000 之间）。
Output
输出
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
对于每个测试用例，您应该输出两行。第一行是 “Case #：”，# 表示测试用例的编号。第二行包含三个整数，序列中的 Max Sum、子序列的开始位置、子序列的结束位置。如果有多个结果，则输出第一个结果。在两个 case 之间输出一个空行。
Sample Input
样本输入
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
示例输出
Case 1:
案例 1：
14 1 4
Case 2:
案例 2：
7 1 6
2. Robberies
2. 抢劫
Problem Description
问题描述
The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.
有抱负的强盗罗伊看过很多美国电影，知道坏人通常会在最后被抓住，通常是因为他们变得太贪婪了。他决定在银行抢劫这个利润丰厚的行业工作一小段时间，然后退休后在一所大学找到了一份舒适的工作。
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
几个月来，Roy 一直在评估各种银行的安全性和持有的现金数量。他想冒一个经过计算的风险，并尽可能多地抓住钱。
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
他的母亲 Ola 已经决定了被抓住的可能性是可以容忍的。她觉得，如果他一起抢劫的银行给出的概率小于这个概率，他就足够安全了。
Input
输入
The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .
输入的第一行给出 T，即事例数。对于每个场景，第一行输入给出一个浮点数 P，即 Roy 需要低于的概率，以及一个整数 N，即他有计划的银行数量。然后跟随 N 行，其中 j 行给出一个整数 Mj 和一个浮点数 Pj 。
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
银行 j 包含 Mj 百万，抢劫被抓到的概率是 Pj 。
Output
输出
For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.
对于每个测试用例，输出一行，其中包含他可以预期获得的最大数百万个，而被捕获的概率小于设置的限制。
Notes and Constraints
约束与限制
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0 < 兆 <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.
如果银行被抢劫，它就会破产，您可能会假设所有可能性都是独立的，因为警方的资金非常少。
Sample Input
样本输入
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
Sample Output
示例输出
2
4
6
3.Employment Planning
3.就业规划
Problem Description
问题描述
A project manager wants to determine the number of the workers needed in every month. He does know the minimal number of the workers needed in each month. When he hires or fires a worker, there will be some extra cost. Once a worker is hired, he will get the salary even if he is not working. The manager knows the costs of hiring a worker, firing a worker, and the salary of a worker. Then the manager will confront such a problem: how many workers he will hire or fire each month in order to keep the lowest total cost of the project.
项目经理想要确定每个月所需的工作人员数量。他确实知道每个月需要的最小工人数量。当他雇用或解雇工人时，会有一些额外的成本。一旦工人被录用，即使他不工作，他也会得到薪水。经理知道雇用工人、解雇工人的成本以及工人的工资。那么经理将面临这样的问题：他每个月将雇用或解雇多少工人，以保持项目的最低总成本。
Input
输入
The input may contain several data sets. Each data set contains three lines. First line contains the months of the project planed to use which is no more than 12. The second line contains the cost of hiring a worker, the amount of the salary, the cost of firing a worker. The third line contains several numbers, which represent the minimal number of the workers needed each month. The input is terminated by line containing a single '0'.
输入可能包含多个数据集。每个数据集包含三行。第一行包含计划使用的项目的月份，不超过 12 个月。第二行包含雇用工人的成本、工资金额、解雇工人的成本。第三行包含多个数字，表示每月所需的最小工作人员数量。input 由包含单个 '0' 的行终止。
Output
输出
The output contains one line. The minimal total cost of the project.
输出包含一行。项目的最低总成本。
Sample Input
样本输入
3
4 5 6
10 9 11
0
Sample Output
示例输出
199
4.Attack on Titans
4.进击的巨人
Problem Description
问题描述
Over centuries ago, mankind faced a new enemy, the Titans. The difference of power between mankind and their newfound enemy was overwhelming. Soon, mankind was driven to the brink of extinction. Luckily, the surviving humans managed to build three walls: Wall Maria, Wall Rose and Wall Sina. Owing to the protection of the walls, they lived in peace for more than one hundred years.
几个世纪前，人类面临着一个新的敌人，泰坦。人类和他们新发现的敌人之间的力量差距是压倒性的。很快，人类就被推向了灭绝的边缘。幸运的是，幸存的人类设法建造了三堵墙：玛丽亚墙、玫瑰墙和新浪墙。由于城墙的保护，他们和平生活了一百多年。
But not for long, a colossal Titan appeared out of nowhere. Instantly, the walls were shattered, along with the illusory peace of everyday life. Wall Maria was abandoned and human activity was pushed back to Wall Rose. Then mankind began to realize, hiding behind the walls equaled to death and they should manage an attack on the Titans.
但没过多久，一个巨大的泰坦凭空出现。瞬间，墙壁被打破，日常生活的虚幻宁静也被打破。玛丽亚墙被遗弃，人类活动被推回玫瑰墙。然后人类开始意识到，躲在墙后等于死亡，他们应该设法攻击泰坦。
So, Captain Levi, the strongest ever human being, was ordered to set up a special operation squad of N people, numbered from 1 to N. Each number should be assigned to a soldier. There are three corps that the soldiers come from: the Garrison, the Recon Corp and the Military Police. While members of the Garrison are stationed at the walls and defend the cities, the Recon Corps put their lives on the line and fight the Titans in their own territory. And Military Police serve the King by controlling the crowds and protecting order. In order to make the team more powerful, Levi will take advantage of the differences between the corps and some conditions must be met.
因此，有史以来最强壮的人类李维上尉奉命组建一支由 N 人组成的特别行动小队，编号从 1 到 N。每个数字都应该分配给一名士兵。士兵来自三个军团：驻军、侦察兵团和宪兵队。当驻军成员驻扎在城墙并保卫城市时，侦察军团冒着生命危险在自己的领土上与泰坦作战。宪兵通过控制人群和保护秩序来为国王服务。为了让团队更加强大，李维会利用军团之间的差异，必须满足一些条件。
The Garrisons are good at team work, so Levi wants there to be at least M Garrison members assigned with continuous numbers. On the other hand, members of the Recon Corp are all elite forces of mankind. There should be no more than K Recon Corp members assigned with continuous numbers, which is redundant. Assume there is unlimited amount of members in each corp, Levi wants to know how many ways there are to arrange the special operation squad.
驻军擅长团队合作，因此 Levi 希望至少有 M 名驻军成员被分配有连续的编号。另一方面，侦察兵团的成员都是人类的精英力量。分配有连续编号的 K Recon Corp 成员不应超过，这是多余的。假设每个公司的成员数量不受限制，Levi 想知道有多少种方法可以安排特别行动小队。
Input
输入
There are multiple test cases. For each case, there is a line containing 3 integers N (0 < N < 1000000), M (0 < M < 10000) and K (0 < K < 10000), separated by spaces.
有多个测试用例。对于每种情况，都有一行包含 3 个整数 N （0 < N < 1000000）、M （0 < M < 10000） 和 K （0 < K < 10000），用空格分隔。
Output
输出
One line for each case, you should output the number of ways mod 1000000007.
每种情况都有一行，你应该输出 mod 1000000007 的方式数量。
Sample Input
样本输入
3 2 2
Sample Output
示例输出
5
5. The King’s Ups and Downs
5. 国王的起起落落
Problem Description
问题描述
The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than the guards next to him or taller than the guards next to him (so the heights go up and down along the line). For example, seven guards of heights 160, 162, 164, 166, 168, 170 and 172 cm. could be arranged as:
国王有各种不同高度的守卫。他不是按照身高递增或递减的顺序排列他们，而是想让他们排成一排，这样每个守卫要么比他旁边的守卫矮，要么比他旁边的守卫高（所以高度会沿着这条线上下波动）。例如，身高为 160、162、164、166、168、170 和 172 厘米的七个守卫可以排列为：
or perhaps:
或者：
The king wants to know how many guards he needs so he can have a different up and down order at each changing of the guard for rest of his reign. To be able to do this, he needs to know for a given number of guards, n, how many different up and down orders there are:
国王想知道他需要多少守卫，这样他就可以在他统治的剩余时间里在每次换卫时有不同的上下顺序。为了能够做到这一点，他需要知道给定数量的守卫 n，有多少种不同的上下顺序：
For example, if there are four guards: 1, 2, 3,4 can be arrange as:
例如，如果有四个守卫：1、2、3、4 可以排列为：
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
For this problem, you will write a program that takes as input a positive integer n, the number of guards and returns the number of up and down orders for n guards of differing heights.
对于这个问题，你将编写一个程序，该程序以正整数 n（守卫的数量）作为输入，并返回 n 个不同高度的守卫的上下订单数。
Input
输入
The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set consists of single line of input containing two integers. The first integer, D is the data set number. The second integer, n (1 <= n <= 20), is the number of guards of differing heights.
输入的第一行包含一个整数 P，（1 <= P <= 1000），这是后面的数据集的数量。每个数据集由一行包含两个整数的输入组成。第一个整数 D 是数据集编号。第二个整数 n （1 <= n <= 20） 是不同身高的守卫数量。
Output
输出
For each data set there is one line of output. It contains the data set number (D) followed by a single space, followed by the number of up and down orders for the n guards.
对于每个数据集，有一行输出。它包含数据集编号 （D），后跟一个空格，后跟 n 个守卫的上下订单数。
Sample Input
样本输入
4
1 1
2 3
3 4
4 20
Sample Output
示例输出
1 1
2 4
3 10
6.Number String
6.数字字符串
Problem Description
问题描述
The signature of a permutation is a string that is computed as follows: for each pair of consecutive elements of the permutation, write down the letter 'I' (increasing) if the second element is greater than the first one, otherwise write down the letter 'D' (decreasing). For example, the signature of the permutation {3,1,2,7,4,6,5} is "DIIDID".
排列的签名是一个字符串，计算方式如下：对于排列的每对连续元素，如果第二个元素大于第一个元素，则记下字母 'I' （递增），否则记下字母 'D' （递减）。例如，排列 {3,1,2,7,4,6,5} 的签名是 “DIIDID”。
Your task is as follows: You are given a string describing the signature of many possible permutations, find out how many permutations satisfy this signature.
你的任务如下：给你一个字符串，描述许多可能的排列的签名，找出有多少种排列满足这个签名。
Note: For any positive integer n, a permutation of n elements is a sequence of length n that contains each of the integers 1 through n exactly once.
注： 对于任何正整数 n，n 个元素的排列是一个长度为 n 的序列，其中包含整数 1 到 n 中的每个整数都恰好一次。
Input
输入
Each test case consists of a string of 1 to 1000 characters long, containing only the letters 'I', 'D' or '?', representing a permutation signature.
每个测试用例由一个 1 到 1000 个字符长的字符串组成，仅包含字母 'I'、'D' 或 '？'，表示排列签名。
Each test case occupies exactly one single line, without leading or trailing spaces.
每个测试用例只占用一行，没有前导或尾随空格。
Proceed to the end of file. The '?' in these strings can be either 'I' or 'D'.
继续到文件末尾。这些字符串中的 '？' 可以是 'I' 或 'D'。
Output
输出
For each test case, print the number of permutations satisfying the signature on a single line. In case the result is too large, print the remainder modulo 1000000007.
对于每个测试用例，在一行上打印满足签名的排列数。如果结果太大，请打印余数模数1000000007。
Sample Input
样本输入
II
第二
ID
身份证
DI
地
DD
DD 系列
?D
??
Sample Output
示例输出
1
2
2
1
3
6
7. Advanced Fruits
7.高级水果
Problem Description
问题描述
The company "21st Century Fruits" has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesn't work, but sometimes, in very rare cases, a new fruit emerges that tastes like a mixture between both of them.
“21st Century Fruits”公司专门通过将一种水果的基因转移到另一种水果的基因组中来创造新种类的水果。大多数时候这种方法不起作用，但有时，在极少数情况下，会出现一种新的水果，尝起来像是两者之间的混合物。
A big topic of discussion inside the company is "How should the new creations be called?" A mixture between an apple and a pear could be called an apple-pear, of course, but this doesn't sound very interesting. The boss finally decides to use the shortest string that contains both names of the original fruits as sub-strings as the new name. For instance, "applear" contains "apple" and "pear" (APPLEar and apPlEAR), and there is no shorter string that has the same property.
公司内部讨论的一大话题是“新作品应该如何称呼？当然，苹果和梨的混合物可以称为苹果梨，但这听起来不是很有趣。老板最终决定使用最短的字符串，其中包含原始水果的两个名称作为子字符串作为新名称。例如，“applear” 包含 “apple” 和 “pear” （APPLEar 和 apPlEAR），并且没有具有相同属性的较短字符串。
A combination of a cranberry and a boysenberry would therefore be called a "boysecranberry" or a "craboysenberry", for example.
例如，
蔓越莓和波森莓的组合将被称为“boysecranberry”或“craboysenberry”。
Your job is to write a program that computes such a shortest name for a combination of two given fruits. Your algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names.
您的工作是编写一个程序，为两个给定水果的组合计算最短的名称。您的算法应该是高效的，否则它不太可能在分配的时间内执行长水果名称。
Input
输入
Each line of the input contains two strings that represent the names of the fruits that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.
输入的每一行都包含两个字符串，这些字符串表示应合并的水果的名称。所有名称的最大长度为 100，并且仅包含字母字符。
Input is terminated by end of file.
输入在文件结束时终止。
Output
输出
For each test case, output the shortest name of the resulting fruit on one line. If more than one shortest name is possible, any one is acceptable.
对于每个测试用例，在一行中输出结果 fruit 的最短名称。如果可能有多个最短名称，则任何一个都是可接受的。
Sample Input
样本输入
apple peach
苹果桃
ananas banana
阿纳斯香蕉
pear peach
梨桃
Sample Output
示例输出
appleach
苹果
bananas
香蕉
pearch
皮尔奇
8. 龟兔赛跑
Problem Description
问题描述
据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度（VR m/s）一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“"小飞鸽"牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为VT2 m/s。更过分的是，乌龟竟然在跑道上修建了很多很多（N个)的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。
无奈自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，不惜花下血本买了最先进的武器——“”小飞鸽“牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米的距离，以后就只能用脚来蹬了，用脚蹬时的速度为VT2 m/s。更过分的是，竟然在跑道上修建了很多很多（N个）的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。
比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。
Input
输入
本题目包含多组测试，请处理到文件结束。每个测试包括四行：
第一行是一个整数L代表跑道的总长度
第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，开电动车的速度，脚蹬电动车的速度
第四行包含了N(N<=100)个整数p1,p2...pn,分别表示各个充电站离跑道起点的距离，其中0<p1<p2<...<pn<L
第四行包含了N（N<=100）个整数p1，p2...pn，分别表示各个充电站离跑道起点的距离，其中0<p1<p2<...<pn<L
其中每个数都在32位整型范围之内。
Output
输出
当乌龟有可能赢的时候输出一行 “What a pity rabbit!"。否则输出一行"Good job,rabbit!";
当有可能赢的时候输出一行 “真可怜的兔子！”。否则输出一行“Good job，rabbit！”;
题目数据保证不会出现乌龟和兔子同时到达的情况。
Sample Input
样本输入
100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60
Sample Output
示例输出
Good job,rabbit!
干得好，兔子！
What a pity rabbit!
真可惜的兔子！
9. 母牛的故事
9.母牛的故事
Problem Description
问题描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
Input
输入
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n（0<n<55），n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
n=0表示输入数据的结束，不做处理。
Output
输出
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
Sample Input
样本输入
2
4
5
0
Sample Output
示例输出
2
4
6
10. Brackets
10.括弧
Problem Description
问题描述
We give the following inductive definition of a “regular brackets” sequence:
我们给出了 “regular bracket” 序列的归纳定义如下：
the empty sequence is a regular brackets sequence,
空序列是常规的括号序列，
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
如果 s 是常规括号序列，则 （s） 和 [s] 是常规括号序列，并且
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
如果 A 和 B 是常规括号序列，则 AB 是常规括号序列。
no other sequence is a regular brackets sequence
没有其他序列是常规的 Brackets 序列
For instance, all of the following character sequences are regular brackets sequences:
例如，以下所有字符序列都是常规括号序列：
(), [], (()), ()[], ()[()]
while the following character sequences are not:
而以下字符序列则不是：
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.
给定一个括号 字符序列 a1a2 ... AN，您的目标是找到最长的常规括号序列的长度，该序列是 S 的 子序列。也就是说，您希望找到最大的 m ，使得对于索引 i1， i2， ...， im where 1 ≤ i1 < i2 < ... < im ≤ n， a1a2 ... IM 是常规的括号序列。
Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].
给定初始序列 （[（[]]）]，最长的正括号子序列是 [（[]）]。
Input
输入
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
输入测试文件将包含多个测试用例。每个输入测试用例由一行组成，其中仅包含字符 （、）、 ）、 [ 和 ];每个输入测试的长度介于 1 到 100 之间（包括 1 和 100）。文件结尾由包含单词 “end” 的行标记，不应进行处理。
Output
输出
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
对于每种 input 情况，程序应在单行上打印尽可能长的常规括号子序列的长度。
Sample Input
样本输入
((()))
()()()
([]])
)[)(
([][][)
end
结束
Sample Output
示例输出
6
6
4
0
6