Pro.ID21561 TitleVideo Game Combos Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21561 AC2 Submit7 Ratio28.57% 时间&空间限制描述Bessie is playing a video game! In the game, the three letters 'A', 'B', and 'C' are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only N distinct combos possible (1 ≤ N ≤ 20). Combo i is represented as a string Si which has a length between 1 and 15 and contains only the letters 'A', 'B', and 'C'. Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if N = 3 and the three possible combos are "ABA", "CB", and "ABACB", and Bessie presses "ABACB", she will end with 3 points. Bessie may score points for a single combo more than once. Bessie of course wants to earn points as quickly as possible. If she presses exactly K buttons (1 ≤ K ≤ 1,000), what is the maximum number of points she can earn? 输入* Line 1: Two space-separated integers: N and K. * Lines 2..N+1: Line i+1 contains only the string Si, representing combo i. 输出Description Bessie is playing a video game! In the game, the three letters 'A', 'B', and 'C' are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only N distinct combos possible (1 ≤ N ≤ 20). Combo i is represented as a string Si which has a length between 1 and 15 and contains only the letters 'A', 'B', and 'C'. Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if N = 3 and the three possible combos are "ABA", "CB", and "ABACB", and Bessie presses "ABACB", she will end with 3 points. Bessie may score points for a single combo more than once. Bessie of course wants to earn points as quickly as possible. If she presses exactly K buttons (1 ≤ K ≤ 1,000), what is the maximum number of points she can earn? Input * Line 1: Two space-separated integers: N and K. * Lines 2..N+1: Line i+1 contains only the string Si, representing combo i. Output * Line 1: A single integer, the maximum number of points Bessie can obtain. Sample Input 3 7 Sample Output 4 Hint OUTPUT DETAILS: The optimal sequence of buttons in this case is ABACBCB, which gives 4 points--1 from ABA, 1 from ABACB, and 2 from CB. Source 样例输入3 7 样例输出4 提示OUTPUT DETAILS: The optimal sequence of buttons in this case is ABACBCB, which gives 4 points--1 from ABA, 1 from ABACB, and 2 from CB. |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 09:09 , Processed in 0.037524 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
