wls 有一个长度为 nn 的字符串，每次他可以将一个长度不大于 ll 的子串修改成同一种字母，问至少修改多少次可以使字符串最多含有 kk 段。 连续的只含同 一种字母的子串被称为一段。比如说， aaabbccaaa共含有 4 段。
Input
第一行三个整数 n，l，k。 第二行一个字符串。 1 ≤ n ≤ 100, 000 1 ≤ l ≤ 100, 000 1 ≤ k ≤ 10
Output
一行一个数表示答案。
Sample Input
3 1 1 babSample Output
1定义状态 表示第 i 位前分了 j 段，操作后当前字符为 k 的最小操作次数
（1）
当前位不需要修改，直接从第 i - 1 位转移过来，分为两种情况， 和
（2）
当前位需要修改，由于一次最多可以修改L个字符，所以要优先从i - L处转移，同样分为两种情况， 和
可以发现当前的复杂度为，肯定会T，那么我们引入一个表示第 i 位（含）分了 j 段的最小修改次数，每次更新完 之后更新 即可。
引入后的转移方程：
（1）
（2）
前缀优化dp ？就这？
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 1e5 + 7; int dp[N][15][30], pre[N][15]; int main() { int n, p, l; string s; scanf("%d%d%d", &n, &l, &p); cin >> s; s = "#" + s; memset(dp, inf, sizeof(dp)); memset(pre, inf, sizeof(pre)); for(int i = 0; i < 26; ++i) { dp[0][0][i] = 0; dp[1][1][i] = 1; if(s[1] == i + 'a') dp[1][1][i] = 0; } pre[0][0] = 0; pre[1][1] = 0; for(int i = 2; i <= n; ++i) { for(int j = 1; j <= p; ++j) { for(int k = 0; k < 26; ++k) { if(s[i] == k + 'a') dp[i][j][k] = min({dp[i][j][k], dp[i - 1][j][k], pre[i - 1][j - 1]}); else { int id = max(0, i - l); dp[i][j][k] = min({dp[i][j][k], dp[id][j][k] + 1, pre[id][j - 1] + 1}); } pre[i][j] = min(pre[i][j], dp[i][j][k]); } } } int ans = inf; for(int i = 1; i <= p; ++i) for(int j = 0; j < 26; ++j) ans = min(ans, dp[n][i][j]); printf("%d\n", ans); return 0; }
