传送门
题意
给出一个字符串，只包括两个字符 'r' , 'y'，现在可以把 'y' 变成 'r' ,把 'r' 变成 'y'，问最少需要多少次，才能把这个字符串变成 'r...y...r...'模式。
思路
一般这种题目我都是通过枚举端点解决。
字符串下标从 1 开始，设两个分段点分别为 (p_1)，(p_2)。
那么 区间([1,p_1]) 应该全部变为 ('r')，区间([p_1+1，p_2]) 应该变成 ('y')，区间([p_2+1，len])应该变成 ('r')。
我们先枚举 (p_1) 的位置，再枚举 (p_2) 的位置，得到 (p_2) 为任意值时使得区间 ([p_1+1,len])合法的操作次数。
比如 (yyyrryy)
当 (p_1) 为 1 时，(p_2) 分别为 2,3,4,5,6时，使得区间 ([p_1+1,len])合法的操作次数分别为：
3 2 3 4 3
这时我们来看当 (p_1) 的位置往后递推一个时相应的合法操作次数：
2 3 4 3 向后推了一个y
3 4 3 向后推了一个y
3 2 向后推了一个r
1 向后退了一个r
我们可以发现当往后推的这一个字符为 ('y') 时，操作次数不会发生变化，但是如果向后推的是 ('r')，那么整体会 -1。即：对于每一个 (p_2) ，(p_1+1) 也就意味着 ([p_1+1,p_2]) 这一段少一个字符，如果少了一个 ('r') ：区间([p_1+1,p_2])操作次数就会减少，否则不变。而 ([p_2+1,len]) 的操作次数没有发生变化。
首先当 (p_1 ==1) 时，可以求出此时所有 (p_2) 的操作次数，因为这些操作次数只会同时改变。
所以我们可以在 (p_1==1) 的时候就求出所有 (p_1) 的最佳位置。
对于任意一个 (p_1) 其答案为：
[1,p1]的'y'个数 + p1=1时求出的该位置p2的最佳位置的操作次数 - [2,p1]'r'的数量
代码
class Solution {
public:
int minimumOperations(string leaves)
{
int N = 1e5 + 10;
int inf = 0x3f3f3f3f;
int prer[N], prey[N], minn[N],ans[N];
int len = leaves.size();
leaves = "1" + leaves;
for (int i = 1; i <= len; i++) {
prer[i] = prer[i - 1] + (leaves[i] == 'r');
prey[i] = prey[i - 1] + (leaves[i] == 'y');
}
minn[len] = inf;
for (int i = len - 1; i>1; i--) {
ans[i] = prer[i] - prer[1] + prey[len] - prey[i];//求出当p1为1时，p2为i时，使得区间[p1+1,len]合法时的次数
minn[i] = min(ans[i], minn[i + 1]);//求出当p1为i时，使得区间[p1+1,len]合法的最少的操作次数（需减去[2,i]出现过的'r'的数量）
}
int rel = inf;
for (int i = 1; i < len - 1; i++) {//枚举p1
int now = prey[i] + minn[i + 1] - (prer[i] - prer[1]);
rel = min(rel, now);
}
return rel;
}
};