【深基6.习2】honoka的键盘

解题思路

先统计不修改的 VK 数量，再依次翻转每个位置的 V/K，重新统计并取最大，统计后恢复字符。

正确性说明

最多改一个字符的所有方案包括不改和选择一个位置翻转，两类都已枚举；每个方案准确计数，因此最大值最优。

易错点

字符恢复后再尝试下一位置；长度为 1 时没有相邻对。

复杂度

时间 O(n²)，空间 O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    auto countVK = [&]() {
        int c = 0;
        for (int i = 0; i + 1 < n; i++)
            if (s[i] == 'V' && s[i + 1] == 'K')
                c++;
        return c;
    };
    int ans = countVK();
    for (int i = 0; i < n; i++) {
        s[i] = s[i] == 'V' ? 'K' : 'V';
        ans = max(ans, countVK());
        s[i] = s[i] == 'V' ? 'K' : 'V';
    }
    cout << ans << "\n";
    return 0;
}