题解

状态定义（$3$ 个阶段）

• 第 $0$ 段：开头连续的 $r$。
• 第 $1$ 段：中间连续的 $y$。
• 第 $2$ 段：末尾连续的 $r$。

用长度为 $3$ 的数组 $dp$ 表示处理到位置 $i$ 时的最少修改次数：

• $dp[0]$：把前缀变为“只在第 $0$ 段”，即全是 $r$ 的最少修改；
• $dp[1]$：把前缀变为“第 $0$ 段接第 $1$ 段”的最少修改；
• $dp[2]$：把前缀变为“第 $0$ 段接第 $1$ 段接第 $2$ 段”的最少修改。

令当前位置 $i$ 的字符为 $s_i$，定义代价：

• 把 $s_i$ 变成 $r$ 的代价 $c_r(i)=\begin{cases}0,& s_i=r1,& s_i=y\end{cases}$
• 把 $s_i$ 变成 $y$ 的代价 $c_y(i)=\begin{cases}0,& s_i=y1,& s_i=r\end{cases}$

初始化

• 只可能从第 $0$ 段开始，因此有 $dp[0]=c_r(0),dp[1]=+\infty,dp[2]=+\infty$。

状态转移（从左到右迭代 $i=1\ldots n-1$，用上一轮的拷贝 $pre$）

• 第 $0$ 段继续放 $r$： $dp[0]=pre[0]+c_r(i)$
• 第 $1$ 段可以由“继续第 $1$ 段”或“从第 $0$ 段转入”得到，再放 $y$： $dp[1]=\min{pre[0],pre[1]}+c_y(i)$
• 第 $2$ 段可以由“继续第 $2$ 段”或“从第 $1$ 段转入”得到，再放 $r$： $dp[2]=\min{pre[1],pre[2],}+c_r(i)$

答案

• 由于三段都至少 $1$ 个，最终答案为 $dp[2]$（在完整遍历后，第 $2$ 段已被合法开启）。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size();

    const int INF = 1e9;

    // dp[0]：到当前位置属于第0段(r段)的最少修改
    // dp[1]：到当前位置属于第1段(y段)的最少修改
    // dp[2]：到当前位置属于第2段(r段)的最少修改
    array<int, 3> dp{INF, INF, INF};

    auto cr = [&](int i) { return s[i] == 'r' ? 0 : 1; }; // 变成 r 的代价
    auto cy = [&](int i) { return s[i] == 'y' ? 0 : 1; }; // 变成 y 的代价

    // 初始化 i = 0，只能处在第0段
    dp[0] = cr(0);
    dp[1] = INF;
    dp[2] = INF;

    for (int i = 1; i < n; ++i) {
        array<int, 3> pre = dp; // 备份上一位置的三段代价
        dp[0] = pre[0] + cr(i);                     // 继续第0段
        dp[1] = min(pre[0], pre[1]) + cy(i);        // 进入/继续第1段
        dp[2] = min(pre[1], pre[2]) + cr(i);        // 进入/继续第2段
    }

    cout << dp[2] << "\n";
    return 0;
}

Python

import sys

data = sys.stdin.read().strip().split()
if not data:
    sys.exit(0)
s = data[0]
n = len(s)
INF = 10**9

def cr(i):  # 把 s[i] 变成 'r' 的代价
    return 0 if s[i] == 'r' else 1

def cy(i):  # 把 s[i] 变成 'y' 的代价
    return 0 if s[i] == 'y' else 1

# dp[0], dp[1], dp[2] 含义同上
dp0, dp1, dp2 = cr(0), INF, INF

for i in range(1, n):
    pre0, pre1, pre2 = dp0, dp1, dp2
    dp0 = pre0 + cr(i)               # 继续第0段
    dp1 = min(pre0, pre1) + cy(i)    # 进入/继续第1段
    dp2 = min(pre1, pre2) + cr(i)    # 进入/继续第2段

print(dp2)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s == null || s.isEmpty()) return;
        int n = s.length();
        final int INF = 1000000000;

        // dp[0], dp[1], dp[2] 含义同上
        int dp0 = (s.charAt(0) == 'r') ? 0 : 1; // 第0段
        int dp1 = INF;                          // 第1段（初始不可达）
        int dp2 = INF;                          // 第2段（初始不可达）

        for (int i = 1; i < n; i++) {
            int cr = (s.charAt(i) == 'r') ? 0 : 1;
            int cy = (s.charAt(i) == 'y') ? 0 : 1;

            int pre0 = dp0, pre1 = dp1, pre2 = dp2;

            dp0 = pre0 + cr;                 // 继续第0段（r段）
            dp1 = Math.min(pre0, pre1) + cy; // 进入/继续第1段（y段）
            dp2 = Math.min(pre1, pre2) + cr; // 进入/继续第2段（r段）
        }

        System.out.println(dp2);
    }
}

题目描述：

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 $leaves$。字符串 $leaves$ 仅包含小写字符 $r$ 和 $y$，其中字符 $r$ 表示一片红叶，字符 $y$ 表示一片黄叶。出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 $1$。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。

请你帮助小扣计算出他最少需要多少次调整操作才能将秋叶收藏集调整完毕。

输入：

一个字符串 $leaves$，表示秋叶收藏集。字符串的大小满足 $3 ≤ leaves.length ≤ 10^5$，并且字符串中仅包含字符 $r$ 和 $y$。

输出：

输出一个整数，表示最少需要的调整操作次数。

示例 1：

输入：

rrryyyrryyyrr

输出：

2

解释： 调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"。

示例 2：

输入：

ryr

输出：

0