问题1518--字符串变换

1518: 字符串变换

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

给出一个仅包含小写字母的字符串s，你最多可以操作k次，使得任意一个小写字母变为与其相邻的小写字母（ASCII码差值的绝对值为1），请你求出可能的最长相等子序列（即求这个字符串修改至多k次后的的一个最长子序列，且需要保证这个子序列中每个字母相等）。

子序列：从原字符串中取任意多个字母按照先后顺序构成的新的字符串。

输入

两行
第一行为整数k（1=< k <= 3000）
第二行为字符串(字符长度大于等于1，小于等于1024)

输出

最长相等子序列长度

样例输入 Copy 

2
abcde

样例输出 Copy 

3

提示

样例解释：
对于abcde，可以把a变成b，把c变成b，这样得到bbbde，最长相等子序列长度为3

来源/分类

11字符串相关 25初级算法-贪心 
[提交] [状态]