题解：CF1392D Omkar and Bed Wars
majingxuan123
·
·
题解
“遇到 DP 状态无法转移的时候，可以尝试增加状态维数。”—— tf
挑战最劣解。
注意到连续三个字符串只有可能为 LxR、RxL、LRL、RLR，即三个连续的字符不能相同，所以设计如下状态。
$a,b,c$ 很好理解，至于 $d,e$ 是判环是否合法使用的，状态转移显然，自行理解。
请注意一些不合法的状态一定要设为正无穷。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,f[N][2][2][2][2][2];
string s;
int main(){
cin>>T;
while(T--){
cin>>n>>s;
for(int i=n-1;i>=0;i--)s[i+1]=(s[i]=='L'?0:1);
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++){
if(!(i==j&&j==k))f[3][i][j][k][k][j]=(s[1]!=k)+(s[2]!=j)+(s[3]!=i);
else f[3][i][j][k][k][j]=1e9;
f[3][i][j][k][k^1][j]=f[3][i][j][k][k][j^1]=f[3][i][j][k][k^1][j^1]=1e9;
}
for(int i=4;i<=n;i++){
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
for(int c=0;c<2;c++)
for(int d=0;d<2;d++)
for(int e=0;e<2;e++){
f[i][a][b][c][d][e]=1e9;
if(a==b&&b==c)continue;
for(int g=0;g<2;g++)
f[i][a][b][c][d][e]=min(f[i][a][b][c][d][e],f[i-1][b][c][g][d][e]+(s[i]!=a));
}
}
int ans=1e9;
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
for(int c=0;c<2;c++)
for(int d=0;d<2;d++)
for(int e=0;e<2;e++)
if(!(a==b&&a==d)&&!(a==d&&d==e))ans=min(ans,f[n][a][b][c][d][e]);
cout<<ans<<'\n';
}
return 0;
}
```
时间复杂度：$O(n)$。
然而有 $64$ 倍的常数。
虽然很难写，但是最无脑，~还可以获得最劣解~。