区间 DP

区间 DP（预处理）
思路
设 cost[ l ][ r ] 表示子串 s[ l . . . r ] 变成回文串的最小修改次数。
状态转移：

• 若 s[l]=s[r]，两端已经对称，问题缩为 s[ l + 1 . . . r − 1 ]
• 若 s[l]=s[r] ，必须修改其中一端，次数 +1 ，cost[ l ][ r ] = cost[ l + 1 ][ r − 1 ] + [ s[ l ] = s[ r ] ]

按子串长度从小到大枚举。

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

int cost[205][205];

int main() {
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();

    // 按长度从小到大枚举
    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            cost[l][r] = cost[l + 1][r - 1] + (s[l] != s[r]);
        }
    }

    long long ans = 0;
    for (int l = 0; l < n; l++)
        for (int r = l; r < n; r++)
            if (cost[l][r] <= k) ans++;

    cout << ans;
    return 0;
}