Statement

简单题，但是题解貌似没有 dp 做法。

给定一段长度为 nn 的 0101 字符串，允许至多反转其中一段区间，求满足 0101 相间要求的最大长度。

Solution

很典的状态机，不难想到一共有三种状态：

  • 还没有进行反转
  • 正在进行反转
  • 已经反转完成

我们用 fi,0/1/2f_{i, 0/1/2} 分别表示第 ii 个数处于以上三种状态时候的最大长度，不难思考得出三者之间的状态转移如下：

fi−1,0→fi,0fi−1,1,fi−1,0→fi,1fi−1,1,fi−1,2→fi,2f_{i - 1, 0} \to f_{i, 0}\\ f_{i - 1, 1}, f_{i - 1, 0} \to f_{i, 1}\\ f_{i - 1, 1}, f_{i - 1, 2} \to f_{i, 2}

初始状态当然有 f1,0=f1,1=1,f1,2=−∞f_{1, 0} = f_{1, 1} = 1, f_{1, 2} = -\infin​，根据状态方程模拟即可，具体可以看代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
f[1][0] = f[1][1] = 1, ans = 0;
for (int i = 2; i <= n; i ++)
{
    if (a[i] == a[i - 1])
    {
        f[i][0] = 1;
        f[i][1] = f[i - 1][0] + 1;
        f[i][2] = f[i - 1][1] + 1;
    }
    else
    {
        f[i][0] = f[i - 1][0] + 1;
        f[i][1] = f[i - 1][1] + 1;
        f[i][2] = f[i - 1][2] + 1;
    }
    ans = max(ans, *max_element(f[i], f[i] + 3));
}
cout << ans << '\n';

以上代码可以过了，但是不够优美，不难发现可以直接省略掉第一维，代码十分精简。

1
2
3
4
5
6
7
8
9
10
g[0] = g[1] = 1, ans = 0;
for (int i = 2; i <= n; i ++)
{
    if (a[i] == a[i - 1])
        g[2] = g[1] + 1, g[1] = g[0] + 1, g[0] = 1;
    else
        g[2] ++, g[1] ++, g[0] ++;
    ans = max(ans, *max_element(g, g + 3));
}
cout << ans << '\n';