#2580. [Usaco2012 Jan]Video Game

[Usaco2012 Jan]Video Game

题目描述

Bessie is playing a video game! In the game, the three letters ' AA ', ' BB ', and ' CC ' are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only NN distinct combos possible ( 1N201 \le N \le 20 ). Combo i is represented as a string SiS_i which has a length between 11 and 1515 and contains only the letters ' AA ', ' BB ', and ' CC '. 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=3N=3 and the three possible combos are " ABAABA ", " CBCB ", and " ABACBABACB ", and Bessie presses " ABACBABACB ", she will end with 33 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 KK buttons ( 1K1,0001 \le K \le 1,000 ), what is the maximum number of points she can earn?

题意简述:给出 nnABCABCcombo[1..n]combo[1..n]kk ,现要求生成一个长 kk 的字符串 SS,问 SSword[1..n]word[1..n] 的最大匹配数

输入格式

Line 11 : Two space-separated integers: NN and KK .

Lines 2..N+12..N+1 : Line i+1i+1 contains only the string SiS_i , representing combo ii .

输出格式

Line 11 : A single integer, the maximum number of points Bessie can obtain.

3 7 ABA CB ABACB
4

提示

The optimal sequence of buttons in this case is ABACBCBABACBCB , which gives 44 points-- 11 from ABAABA, 11 from ABACBABACB , and 22 from CBCB.