题解 CF1392D 【Omkar and Bed Wars】

题解 - $\mathrm{P}1392\mathrm{D}$

题目描述

题目传送门

$\mathrm{S}\mathrm{o}\mathrm{l}$

好像大家都是找规律做法，我提供一种 dp 的做法

设 $f_{i,j,k}$ 表示到第 $i$ 个人攻击方向为 $j\in [0,1]$ 当前受到 $k\in [0,1,2]$ 个人攻击的最少修改次数。

我们每次枚举上一个人的攻击方向 $lj$ 以及受到攻击次数 $lk$ 进行转移。分 $4$ 种情况进行讨论：

• $i$ 和 $i-1$ 攻击方向相同且攻击左边，那么此时转移的条件为 $lk=2$ 因为只有受到两个人的攻击才能往任意方向进攻，此时 $i$ 可能受到 $0\sim 1$ 个攻击来自 $i+1$。所以转移为 $f_{i,0,0/1}=\min (f_{i-1,lj,lk}+[s_i{=}^{\prime }{R}^{\prime }])[lk==2]$

• 对于 $i$ 和 $i-1$ 都攻击右边的转移为：$f_{i,1,2}=\min (f_{i-1,lj,lk}+[s_i{=}^{\prime }{L}^{\prime }])[lk<2]$

• 对于 $i$ 攻击左边，$i-1$ 攻击右边那么转移为：$f_{i,0,0/1}=\min (f_{i-1,lj,lk}+[s_i={=}^{\prime }{L}^{\prime }])[lk<2]$

• 对于 $i$ 攻击右边，$i-1$ 攻击左边那么转移为：$f_{i,1,1/2}=\min (f_{i-1,lj,lk}+[s_i={=}^{\prime }{R}^{\prime }])[lk>0]$

时间复杂度：$O(\sum n)$ 附加一个大常数

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

const int N=2e5+5;

char a[N];
int Q,n,ans,f[N][2][4];

inline int C(char c) { return (c=='R')?1:0; }

int main()
{
	io.read(Q);
	for (;Q--;)
	{
		io.read(n);
		scanf("%s",a+1);
		//0:left 1:right 
		int ans=1e9;
		For(j,0,1) For(k,0,2) 
		{
			For(i,0,n+1) mem(f[i],88);
			f[0][j][k]=0;
			For(i,1,n) For(jj,0,1) For(kk,0,2) For(Newj,0,1) 
			{
				int Newk;
				if(jj==Newj&&jj&&kk<2) f[i][Newj][2]=min(f[i][Newj][2],f[i-1][jj][kk]+(C(a[i])^Newj));
				if(jj==Newj&&!jj&&kk==2) For(Newk,0,1) f[i][Newj][Newk]=min(f[i][Newj][Newk],f[i-1][jj][kk]+(C(a[i])^Newj));
				if(jj!=Newj&&jj&&kk>0) For(Newk,1,2) f[i][Newj][Newk]=min(f[i][Newj][Newk],f[i-1][jj][kk]+(C(a[i])^Newj));
				if(jj!=Newj&&!jj&&kk<2) For(Newk,0,1) f[i][Newj][Newk]=min(f[i][Newj][Newk],f[i-1][jj][kk]+(C(a[i])^Newj));
			}
			ans=min(ans,f[n][j][k]);
		}
		io.write(ans);
		puts("");
	}
	return 0;
}
/*
1
6
LRRRRL
*/