核心思路

• 对于第 $k$ 个块，原本两位记为$a, b$。若把该块改成 $[v, v]$，代价是 $\text{cost}_k(v)$=$\mathbf{1}[a\ne v]$+$\mathbf{1}[b\ne v]$=$2$-$\mathbf{1}[a=v]$-$\mathbf{1}[b=v]$ 它只可能是 $0,1,2$ 三种情况： 若 $a=b=v$ 则代价为 $0$；若 $v\in{a,b}$ 且 $a\ne b$ 则代价为 $1$；否则为 $2$。

• 相邻块必须选择不同的 $v$。因此做一维按块推进、按末尾选值的动态规划：

  • 设 $m=\frac{n}{2}$ 为块数，数字候选为 $v\in{0,\dots,9}$。
  • 定义 $\text{dp}_{k}(v)$=$\text{使前 }k$$\text{ 个块满足要求且第 }k$$\text{ 块取值为 }v$$\text{ 的最小代价}$
  • 转移： $\text{dp}_k(v)$=$\text{cost}_k(v)$+$\min_{u/nev}$$\text{dp}_{k-1}(u)$
  • 初值：$\text{dp}_1(v)=\text{cost}_1(v)$
  • 答案：$\min_{v}\text{dp}_{m}(v)$

• 状态数 $10$，每块做 $10\times 10$ 的转移，整体复杂度 $O(n)$，常数小，足以通过 $n\le 2\times 10^5$。

C++

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

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

    int m = n / 2;                     // 块数
    const int DIG = 10;                // 数字范围 0..9
    const int INF = 1e9;

    // dp_prev[v]: 处理到上一个块，且上一个块取值为 v 的最小代价
    vector<int> dp_prev(DIG, INF), dp_cur(DIG, INF);

    for (int k = 0; k < m; ++k) {
        int a = s[2 * k] - '0';
        int b = s[2 * k + 1] - '0';

        // 计算本块改成 [v,v] 的代价 cost_k[v]
        int cost[ DIG ];
        for (int v = 0; v < DIG; ++v) {
            int c = 0;
            if (a != v) ++c;
            if (b != v) ++c;
            cost[v] = c; // 0/1/2
        }

        if (k == 0) {
            // 初始块，无相邻约束，只需本块代价
            for (int v = 0; v < DIG; ++v) dp_cur[v] = cost[v];
        } else {
            // 一般块：dp[k][v] = cost_k[v] + min_{u != v} dp[k-1][u]
            for (int v = 0; v < DIG; ++v) {
                int best = INF;
                for (int u = 0; u < DIG; ++u) {
                    if (u == v) continue; // 相邻块的取值必须不同
                    best = min(best, dp_prev[u]);
                }
                dp_cur[v] = best + cost[v];
            }
        }

        dp_prev.swap(dp_cur);
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    int ans = *min_element(dp_prev.begin(), dp_prev.end());
    cout << ans << "\n";
    return 0;
}

Python

import sys

def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    s = data[1].strip()
    m = n // 2  # 块数
    DIG = 10
    INF = 10**9

    dp_prev = [INF] * DIG
    dp_cur = [INF] * DIG

    for k in range(m):
        a = ord(s[2 * k]) - ord('0')
        b = ord(s[2 * k + 1]) - ord('0')

        # 本块改成 [v,v] 的代价
        cost = [0] * DIG
        for v in range(DIG):
            c = 0
            if a != v: c += 1
            if b != v: c += 1
            cost[v] = c  # 0/1/2

        if k == 0:
            # 初始块
            for v in range(DIG):
                dp_cur[v] = cost[v]
        else:
            # 转移：相邻块的取值必须不同
            for v in range(DIG):
                best = INF
                for u in range(DIG):
                    if u == v:
                        continue
                    if dp_prev[u] < best:
                        best = dp_prev[u]
                dp_cur[v] = best + cost[v]

        dp_prev, dp_cur = dp_cur, [INF] * DIG

    print(min(dp_prev))

if __name__ == "__main__":
    solve()

Java

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

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        String s = fs.next();
        int m = n / 2;          // 块数
        final int DIG = 10;
        final int INF = 1_000_000_000;

        int[] dpPrev = new int[DIG];
        int[] dpCur  = new int[DIG];
        Arrays.fill(dpPrev, INF);
        Arrays.fill(dpCur, INF);

        for (int k = 0; k < m; k++) {
            int a = s.charAt(2 * k) - '0';
            int b = s.charAt(2 * k + 1) - '0';

            // cost[v] = 本块变成 [v,v] 的代价
            int[] cost = new int[DIG];
            for (int v = 0; v < DIG; v++) {
                int c = 0;
                if (a != v) c++;
                if (b != v) c++;
                cost[v] = c; // 0/1/2
            }

            if (k == 0) {
                for (int v = 0; v < DIG; v++) dpCur[v] = cost[v];
            } else {
                for (int v = 0; v < DIG; v++) {
                    int best = INF;
                    for (int u = 0; u < DIG; u++) {
                        if (u == v) continue;     // 相邻块取值不同
                        if (dpPrev[u] < best) best = dpPrev[u];
                    }
                    dpCur[v] = best + cost[v];
                }
            }

            int[] tmp = dpPrev; dpPrev = dpCur; dpCur = tmp;
            Arrays.fill(dpCur, INF);
        }

        int ans = INF;
        for (int v = 0; v < DIG; v++) ans = Math.min(ans, dpPrev[v]);
        System.out.println(ans);
    }

    // 简单快速读入
    static class FastScanner {
        BufferedInputStream in;
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = new BufferedInputStream(is); }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && Character.isWhitespace(c));
            if (c == -1) return null;
            do {
                sb.append((char)c);
            } while ((c = read()) != -1 && !Character.isWhitespace(c));
            return sb.toString();
        }
        int nextInt() throws IOException { return Integer.parseInt(next()); }
    }
}

题目内容

小李在学数学，她头痛欲裂，请你快来帮帮她。

小李面前有 $n$ 个 $1$ 位数字(保证 $n$ 为偶数，数字为 $0-9$ )。她希望每次改变一个数字的值，请你帮她计算，她至少需要修改几个数字的值才能保证这个数列的第 $2i+1$ 和 $2i+2$ 位 $(0<=i<=n/2-1)$ 数字相同，第 $2i$ 和第 $2i+1$ 位 $(1<=i<=n/2-1)$ 数字不同？($1234$ 的第 $1$ 位数字位 $1$ ，第二位数字是 $2$ ，没有第 $0$ 位数字)

输入描述

第一行包括一个正整数 $n$ ，$n$ 不大于 $2e5$ 且为偶数。

第二行包括连续的 $n$ 位数字，为 $0-9$ 。

输出描述

输出一个整数，表示小李最少需要修改几个数字才能满足要求。

样例1

输入

8
11233298

输出

3

说明

其中一种可行的方法为，修改成 $11223399$，需要修改 $3$ 次，可以证明没有更少的次数满足条件。