此题考察算法： 动态规划,dp \colorbox{#E74C3C}{\color{white}动态规划,dp} 动态规划,dp。
思路
状态：
| 定义 | 前面是否有子串翻转 | 当前第 i i i 数字是否反转 |
|---|---|---|
| d p i , 0 dp_{i,0} dpi,0 | 否 | 否 |
| d p i , 1 dp_{i,1} dpi,1 | 是 | 否 |
| d p i , 2 dp_{i,2} dpi,2 | 否 | 是 |
初始值
因为无论如何，第 1 1 1 个形成的子序列长度是 1 1 1。所以
{ d p 1 , 0 = 1 d p 1 , 1 = 1 d p 1 , 2 = 1 \begin{cases}dp_{1,0}=1\\dp_{1,1}=1\\dp_{1,2}=1\end{cases} ⎩⎪⎨⎪⎧dp1,0=1dp1,1=1dp1,2=1
转移方程
对于所有满足条件的 i ( 2 ≤ i ≤ n ) i(2\le i \le n) i(2≤i≤n)，当 a i = a i − 1 a_i=a_{i-1} ai=ai−1 时：
- d p i , 0 dp_{i,0} dpi,0
因为第 i i i 个不反转，前面的也不翻转，得出递推式：
d p i , 0 = d p i − 1 , 0 dp_{i,0}=dp_{i-1,0} dpi,0=dpi−1,0
- d p i , 1 dp_{i,1} dpi,1
因为第 i i i 个不反转，前面的会翻转，要么第 i − 1 i-1 i−1 个翻转（他俩本相同，当前又不翻转，则不同，长度需加 1 1 1），要么第 i − 1 i-1 i−1 个之前早就翻转完了。得出递推式：
d p i , 1 = max { d p i − 1 , 2 + 1 d p i − 1 , 1 dp_{i,1}=\max\begin{cases}dp_{i-1,2}+1\\dp_{i-1,1}\end{cases} dpi,1=max{ dpi−1,2+1dpi−1,1
- d p i , 2 dp_{i,2} dpi,2
因为第 i i i 个要反转，前面的都无法翻转，要么第 i − 1 i-1 i−1 个翻转，要么前面的都不翻转（他和前面的相同，前面的没翻转，则不同，长度需加 1 1 1）。得出递推式：
d p i , 2 = max { d p i − 1 , 2 d p i − 1 , 0 + 1 dp_{i,2}=\max\begin{cases}dp_{i-1,2}\\dp_{i-1,0}+1\end{cases} dpi,2=max{ dpi−1,2dpi−1,0+1
对于 a i ≠ a i − 1 a_i\not=a_{i-1} ai=ai−1 时：
- d p i , 0 dp_{i,0} dpi,0
因为第 i i i 个不反转，前面的也不翻转，另外前面的与当前不同，长度需加 1 1 1，得出递推式：
d p i , 0 = d p i − 1 , 0 + 1 dp_{i,0}=dp_{i-1,0}+1 dpi,0=dpi−1,0+1
- d p i , 1 dp_{i,1} dpi,1
因为第 i i i 个不反转，前面的会翻转，要么第 i − 1 i-1 i−1 个翻转，要么第 i − 1 i-1 i−1 个之前早就翻转完了（他和前面的不同，前面和当前的都没翻转，则还是不同，长度需加 1 1 1）。得出递推式：
d p i , 1 = max { d p i − 1 , 2 d p i − 1 , 1 + 1 dp_{i,1}=\max\begin{cases}dp_{i-1,2}\\dp_{i-1,1}+1\end{cases} dpi,1=max{ dpi−1,2dpi−1,1+1
- d p i , 2 dp_{i,2} dpi,2
因为第 i i i 个要反转，前面的都无法翻转，要么第 i − 1 i-1 i−1 个翻转（他和前面的不同，前面和当前的都翻转了，则还是不同，长度需加 1 1 1），要么前面的都不翻转。得出递推式：
d p i , 2 = max { d p i − 1 , 2 + 1 d p i − 1 , 0 dp_{i,2}=\max\begin{cases}dp_{i-1,2}+1\\dp_{i-1,0}\end{cases} dpi,2=max{ dpi−1,2+1dpi−1,0
综上所述，状态转移方程是：
{ d p i , 0 = { d p i − 1 , 0 ( a i = a i − 1 ) d p i − 1 , 0 + 1 ( a i ≠ a i − 1 ) d p i , 1 = { max { d p i − 1 , 2 + 1 d p i − 1 , 1 ( a i = a i − 1 ) max { d p i − 1 , 2 d p i − 1 , 1 + 1 ( a i ≠ a i − 1 ) d p i , 2 = { max { d p i − 1 , 2 d p i − 1 , 0 + 1 ( a i = a i − 1 ) max { d p i − 1 , 2 + 1 d p i − 1 , 0 ( a i ≠ a i − 1 ) \begin{cases}dp_{i,0}=\begin{cases}dp_{i-1,0}(a_i=a_{i-1})\\dp_{i-1,0}+1(a_i≠a_{i-1})\end{cases}\\dp_{i,1}=\begin{cases}\max\begin{cases}dp_{i-1,2}+1\\dp_{i-1,1}\end{cases}(a_i=a_{i-1})\\\max\begin{cases}dp_{i-1,2}\\dp_{i-1,1}+1\end{cases}(a_i≠a_{i-1})\end{cases}\\dp_{i,2}=\begin{cases}\max\begin{cases}dp_{i-1,2}\\dp_{i-1,0}+1\end{cases}(a_i=a_{i-1})\\\max\begin{cases}dp_{i-1,2}+1\\dp_{i-1,0}\end{cases}(a_i≠a_{i-1})\end{cases}\end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧dpi,0={ dpi−1,0(ai=ai−1)dpi−1,0+1(ai=ai−1)dpi,1=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧max{ dpi−1,2+1dpi−1,1(ai=ai−1)max{ dpi−1,2dpi−1,1+1(ai=ai−1)dpi,2=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧max{ dpi−1,2dpi−1,0+1(ai=ai−1)max{ dpi−1,2+1dpi−1,0(ai=ai−1)
知道了上面那个奇怪无比的递推式，思路也就显而易见。
输出结果
由于每一种情况都已经考虑，所以只需要输出 max { d p n , 0 d p n , 1 d p n , 2 \max\begin{cases}dp_{n,0}\\dp_{n,1}\\dp_{n,2}\end{cases} max⎩⎪⎨⎪⎧dpn,0dpn,1dpn,2 即可
code
#include<bits/stdc++.h>
#define ll long long
#define ull usigned ll
#define inl inline
using namespace std;
const int maxn=0;
int a[1000005],dp[1000005][3],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
//单个字符读入
char ch;
cin>>ch;
a[i]=ch-'0';
}
dp[1][0]=dp[1][1]=dp[1][2]=1;//初始化
for(int i=2;i<=n;i++){
//动态规划
if(a[i]==a[i-1]){
dp[i][0]=dp[i-1][0];
dp[i][1]=max(dp[i-1][2]+1,dp[i-1][1]);
dp[i][2]=max(dp[i-1][2],dp[i-1][0]+1);
}
else{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=max(dp[i-1][1]+1,dp[i-1][2]);
dp[i][2]=max(dp[i-1][2]+1,dp[i-1][0]);
}
}
cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]);//输出最大值即可
return 0;
}
update timw:2021-8-10
修改了管理员提出的错误