用c++写出这道题:卢老师周末又带娃去游乐场了。这次游乐场出了一个新的小游戏大屏幕上有一个只包含大写字母的字符串 s和一个整数 k 。每一次你可以把任意一个大写字母变成变为和它相邻的大写字母ASCII码差值的绝对值为1这样的操作最多可以进行 k 次。每个人都可以参加谁得到的相等子序列每个字母都相同长度最长谁就能得到一份亲子大礼包。请你帮助卢老师计算最长的相等子序列长度是多少?输入格式输入一行一个整
思路:
- 首先,固定一个字符,然后在k次操作内,尽可能多的将其余相同字符变成该字符。这是因为对于相等子序列,每个字符都必须相同。
- 具体地,对于每个字符c,假设有cnt个c,那么我们可以枚举所有的字符d,如果|d-c|<=k,则可以将所有的d变成c,使得相等子序列长度增加cnt。
- 最后,枚举所有字符,找到相等子序列长度的最大值即可。
时间复杂度:O(n^2k),其中n为字符串长度。
原文地址: https://www.cveoy.top/t/topic/hpyF 著作权归作者所有。请勿转载和采集!