核心思路

对于第 $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}$ 。

P3736.第1题-小李学数学

1000ms

Tried: 157

Accepted: 34

Difficulty: 4

所属公司 : 京东

算法与标签>动态规划

题目内容

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

小李面前有 $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

输出

说明

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

输入

预期输出（选填）

核心思路

P3736.第1题-小李学数学

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About