CF603A Alternative Thinking 题解

题目链接：CF603A Alternative Thinking

题意：

现有一个长度为 $n$ 的 01 串, 可以进行一次区间翻转 ( 起点终点随意, 并且区间里的值 1 变 0, 0 变 1 ), 得到一个新的 01 串, 使得得到的新的 01 串中的一个子串最长 (子串不一定连续), 且这个子串是 01 间隔的，没有连续两个字符相同。比如 0101 , 101 和1010 是合法的, 100, 1100 是不合法的。试求翻转后最长 01 间隔子串的长度.

输入格式：

The first line contains the number of questions on the olympiad $n ~(1\le n \le 10^5)$.

The following line contains a binary string of length $n$ representing Kevin’s results on the USAICO.

输出格式：

Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.

题面啥的懒得修了，看得懂就好（大雾）

这题一开始还以为要什么子序列，结果一看，这玩意在dp的时候贪心选就好了。

设 $f_{i,j}$ 表示前 $i$ 个字符的答案：

• 当 $j = 0$ 时，表示第 $i$ 个字符不翻转，并且没有使用过翻转操作。
• 当 $j = 1$ 时，表示第 $i$ 个字符不翻转，并且使用过翻转操作
• 当 $j = 2$ 时，表示第 $i$ 个字符要翻转。

考虑转移。当 $a_i = a_{i-1}$ 时，有

$$\begin{aligned} & f_{i, 0}=f_{i-1,0} \\ & f_{i, 1}=\max \left(f_{i-1,2}+1, f_{i-1,1}\right) \\ & f_{i, 2}=\max \left(f_{i-1,2}, f_{i-1,0}+1\right) \end{aligned}$$

否则

$$\begin{aligned} & f_{i, 0}=f_{i-1,0}+1 \\ & f_{i, 1}=\max \left(f_{i-1,1}+1, f_{i-1,2}\right) \\ & f_{i, 2}=\max \left(f_{i-1,2}+1, f_{i-1,0}\right) \end{aligned}$$

边界：$f(1,j) = 1$ 。最后的答案为 $\max\{f(n,j)\}$ 。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,f[N][3]; char a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (a + 1); f[1][0] = f[1][1] = f[1][2] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(a[i] == a[i - 1])
        {
            f[i][0] = f[i - 1][0];
            f[i][1] = max(f[i - 1][2] + 1, f[i - 1][1]);
            f[i][2] = max(f[i - 1][2], f[i - 1][0] + 1);
        }else 
        {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = max(f[i - 1][1] + 1, f[i - 1][2]);
            f[i][2] = max(f[i - 1][2] + 1, f[i - 1][0]);
        }
    }
    cout << max({f[n][0], f[n][1], f[n][2]}) << '\n';
    return 0;
}