[cf1392d] D. Omkar and bed Wars

TP

The question ：

• Yes n Individuals stand in a circle , Everyone initially has a pointing direction .
• Given a rule of thumb , Just be satisfied ： If a person is pointed out by two people or not at all , He can choose anyone to point to , Otherwise, it must point to the person who points to him .

Ideas ：

• First of all, this is a ring , We can find that linear dp The transfer will have the problem of aftereffect , I.e. transfer to No n Personal time will affect the 1 personal . So we need to eliminate this effect .

1. Multi state settings , Enumerating ring start points .

Reference blog

$Code:$

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define oper(a) operator<(const a&ee)const
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 5, M = 1e7 + 5, INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
char s[N];
int dp[N][2][3];// front  i  Personal processing is completed , The first  i  Personal point  0/1  Direction , At the same time there is  0/1/2  Someone points to him 

int DP() {
    
	int ans = INF;
	for (int j = 0; j <= 1; j++)
		for (int k = 0; k <= 2; k++) {
    
			for (int i = 0; i <= n; i++)mem(dp[i], 0x3f);
				
			// ring dp, Pay attention to the aftereffect , There will be transfer restrictions on the looped parts 
			// So we enumerate each  0  node  （ Ring is equivalent to  n  node ） In state 
			dp[0][j][k] = 0;

			// The state transition situation is divided according to the direction of any two adjacent people and how many people point to them 
			for (int i = 1; i <= n; i++) {
    

				// Both pointed to the right 
				dp[i][1][2] = dp[i - 1][1][0] + (s[i] != 'R');
				// All to the left 
				dp[i][0][0] = dp[i - 1][0][2] + (s[i] != 'L');

				for (int zk = 0; zk <= 2; zk++) {
    
					for (int kk = 0; kk <= 2; kk++) {
    

						//i  People point to the left ,i - 1  People point to the right 
						if (zk != 0 && kk != 0)
							dp[i][0][zk] = min(dp[i][0][zk], dp[i - 1][1][kk] + (s[i] != 'R'));

						//i  People point to the right ,i - 1  People point to the left 
						if (zk != 2 && kk != 2)
							dp[i][1][zk] = min(dp[i][1][zk], dp[i - 1][0][kk] + (s[i] != 'L'));
					}
				}
			}

			// Last , We're here  n  The node state should correspond to the enumerated state , Only in this way can the effectiveness be guaranteed 
			ans = min(ans, dp[n][j][k]);
		}
	return ans;
}

void solve() {
    
	cin >> n >> s + 1;
	cout << DP() << endl;
}

signed main() {
    
	cinios;
	int T = 1; 
	cin >> T;
	for (int i = 1; i <= T; i++)
		solve();
	return 0;
}
/* */

2. Simplify the combination .

Reference blog

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define oper(a) operator<(const a&ee)const
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 5, M = 1e7 + 5, INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
char s[N];
int dp[N];

void change() {
    
	char ch = s[1];
	for (int i = 1; i < n; i++)
		s[i] = s[i + 1];
	s[n] = ch;
}

void DP() {
    
	for (int i = 1; i <= n; i++)dp[i] = INF;
	for (int i = 2; i <= n; i++) {
    
		dp[i] = min(dp[i], dp[i - 2] + (s[i] != 'L') + (s[i - 1] != 'R'));
		if (i >= 3)
			dp[i] = min(dp[i], dp[i - 3] + (s[i] != 'L') + (s[i - 2] != 'R'));
		if (i >= 4)
			dp[i] = min(dp[i], dp[i - 4] + (s[i] != 'L') + (s[i - 1] != 'L') + (s[i - 2] != 'R') + (s[i - 3] != 'R'));
	}
}

void solve() {
    
	cin >> n >> s + 1;
	int ans = INF;
	for (int i = 1; i <= 4; i++) {
    
		DP();
		change();
		ans = min(ans, dp[n]);
	}
	cout << ans << endl;
}

signed main() {
    
	cinios;
	int T = 1; 
	cin >> T;
	for (int i = 1; i <= T; i++)
		solve();
	return 0;
}
/* */