第二种操作是从 $1$ 开始修改的，也就是修改一段前缀，考虑递推。由于操作可逆，所以我们可以转换为将读入的串变为全 A 串所需的最小变换次数。
设 $f_{i,0}$ 表示前 $i$ 个字符均为 A 时的最小变换次数，设 $f_{i,1}$ 表示前 $i$ 个字符均为 B 时的最小变换次数。在处理第 $i$ 个字符时，前 $i - 1$ 个字符只有全 A 或全 B 两种情况，而我们现在可以将前 $i$ 个字符变为全 A 或全 B。令第 $i$ 个字符是 A，进行分类讨论：
$f_{i - 1,0} \to f_{i,0}$ 不需要操作，直接在末尾添上 A。
$f_{i - 1,0} \to f_{i,1}$ 添上 A 后将区间 $[1,i]$ 进行翻转。
$f_{i - 1,1} \to f_{i,0}$ 将区间 $[1,i - 1]$ 进行翻转，之后添上 A。
$f_{i - 1,1} \to f_{i,1}$ 将区间 $[1,i - 1]$ 进行翻转，之后将 A 变为 B 并添上。操作等价于 $f_{i,0} \to f_{i,1}$。
若第 $i$ 个字符是 B 同理。最后的要求全为 A 串，答案也就是 $\min (f_{n,0},f_{n,1} + 1)$。
由于 $f_{i,0},f_{i,1}$ 只与 $f_{i - 1,0},f_{i - 1,1}$ 有关，所以我们可以将 $f$ 数组的第一维滚掉，即空间上的一个优化。
最后代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,f[2][2];
int main ()
{
n = read ();
for (int i = 1;i <= n;++i)
{
char ch;scanf ("%c",&ch);
if (ch == 'A') f[1][0] = min (f[0][0],f[0][1] + 1),f[1][1] = min (f[1][0],f[0][1]) + 1;
else f[1][1] = min (f[0][1],f[0][0] + 1),f[1][0] = min (f[1][1],f[0][0]) + 1;
f[0][0] = f[1][0],f[0][1] = f[1][1];
}
printf ("%d\n",min (f[0][0],f[0][1] + 1));
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
