honoka的键盘

洛谷·深入浅出 · 代码 · cpp · 难度 2/5 · 共 696 字

至多改一个字符最大化 VK 出现次数

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1422
// 题意：只含 V 和 K 的字符串，可至多把其中一个字符改成另一个，求 VK 子串最多出现几次。
// 思路：枚举把每个位置翻转（V<->K），重新统计 VK 个数，取最大值；不翻转也要算进去。
// 复杂度：O(n^2)，n<=100 很宽松。
// 易错点：VK 必须相邻；改一个字符可能影响左右两个 VK，直接枚举最简单可靠。
#include <iostream>
#include <string>
using namespace std;
int countVK(const string &s){
    int c = 0;
    for(int i = 0; i + 1 < s.size(); i++)
        if(s[i] == 'V' && s[i + 1] == 'K') c++;
    return c;
}
int main(){
    int n;
    string s;
    cin >> n >> s;
    int ans = countVK(s);
    for(int i = 0; i < n; i++){
        string t = s;
        t[i] = (t[i] == 'V' ? 'K' : 'V');
        int c = countVK(t);
        if(c > ans) ans = c;
    }
    cout << ans << endl;
    return 0;
}

honoka的键盘

正文

洛谷·深入浅出的其它内容