1650: 字符串压缩B
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:2
Solved:2
Description
行程长度编码是一种常用的字符串压缩方法,它将连续的相同字符(重复2次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串"aabccc",将"aa"替换为"a2","ccc"替换为` "c3"。因此压缩后的字符串变为"a2bc3"。注意,本问题中,压缩时没有在单个字符后附加计数'1'。
给定一个字符串s和一个整数k。你需要从字符串s中删除最多k个字符,以使s的行程长度编码长度最小。请返回删除最多k个字符后,s行程长度编码的最小长度。
Input
第一行,输入字符串s(1<=|s|<=100,s 仅包含小写英文字母)
第二行,输入删除的字符数k(0 <= k <= |s|)
Output
输出行程长度编码的最小长度。
Sample Input Copy
aaabcccd
2
Sample Output Copy
4
HINT
【样例1说明】
在不删除任何内容的情况下,压缩后的字符串是 "a3bc3d" ,长度为 6 。最优的方案是删除 'b' 和 'd',这样一来,压缩后的字符串为 "a3c3" ,长度是 4 。
【输入样例2】
aabbaa
【输出样例2】
2
【样例2说明】
如果删去两个 'b' 字符,那么压缩后的字符串是长度为 2 的 "a4" 。
【输入样例3】
aaaaaaaaaaa
0
【输出样例3】
3
【样例3说明】
由于 k 等于 0 ,不能删去任何字符。压缩后的字符串是 "a11" ,长度为 3 。