CF Global Round 10-D

D.Omkar and Bed Wars

(Description:)

(n)个人站成一个圈，(i)的右边是(i+1)，(n)的右边是(1)。他们初始有一个朝向（朝左/右）。每次操作可以让一个人转向（左变右或相反）。要求不出现连续三个朝左或连续三个朝右的人，求最小操作数

(Solution:)

经典(dp)，令(f[i][a][b][c][d])为从第一个到第(i)个人，前两个状态为(a)和(b)，后两个人状态为(c)和(d)的最小修改次数

转移时要遍历最后三位，保证后三位不一样

最后的答案为首尾相接后没有连续三个相同的状态的最小值

(Code:)

#include<bits/stdc++.h>
#define inf (200005)
using namespace std;
typedef long long lol;
const int N=200005;
int t,n,o[N],f[N][2][2][2][2];
char s[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%s",&n,s+1);
		for(int i=1;i<=n;i++)o[i]=s[i]=='R';
		for(int i=1;i<=n;i++)
			for(int a=0;a<=1;a++)
				for(int b=0;b<=1;b++)
					for(int c=0;c<=1;c++)
						for(int d=0;d<=1;d++)
							f[i][a][b][c][d]=inf;
		for(int a=0;a<=1;a++)
			for(int b=0;b<=1;b++)
				f[2][a][b][a][b]=(o[1]!=a)+(o[2]!=b);
		for(int i=3;i<=n;i++)
			for(int a=0;a<=1;a++)
				for(int b=0;b<=1;b++)
					for(int c=0;c<=1;c++)
						for(int d=0;d<=1;d++)
							for(int e=0;e<=1;e++)
								if(!(c==d&&d==e)){
									f[i][a][b][d][e]=min(f[i][a][b][d][e],f[i-1][a][b][c][d]+(e!=o[i]));
								}
		int ans=inf;
		for(int a=0;a<=1;a++)
			for(int b=0;b<=1;b++)
				for(int c=0;c<=1;c++)
					for(int d=0;d<=1;d++)
						if(!(c==d&&d==a)&&!(d==a&&a==b))
							ans=min(ans,f[n][a][b][c][d]);
		printf("%d
",ans);
	}
	return 0;
}