【CF1392D】D. Omkar and Bed Wars（环形与后效性dp）

TP

题意：

• 有 n 个人站成环形，每个人初始有一个指的方向。
• 给定一个指的规律，满足才行：一个人如果被两个人或者完全没被人指，他就可以随便选一个人指，否则必须指向那个指向他的人。

思路：

• 首先这是一个环形，我们可以发现线性的dp转移会有后效性的问题，即转移到第 n 个人时又会影响第 1 个人。所以需要消除这种影响。

1. 多状态设置，枚举环起点。

参考博客

$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];//前 i 个人处理完毕，第 i 个人指向 0/1 方向，同时有 0/1/2 个人指向他

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);
				
			//环形dp，要注意后效性问题，成环的部分会有转移限制
			//所以我们枚举每一种 0 结点 （环状时相当于 n 结点）处状态
			dp[0][j][k] = 0;

			//根据任意相邻两人的方向和有多少人指向他们来划分状态转移情况
			for (int i = 1; i <= n; i++) {

				//两人都指右
				dp[i][1][2] = dp[i - 1][1][0] + (s[i] != 'R');
				//都指左
				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 人指左，i - 1 人指右
						if (zk != 0 && kk != 0)
							dp[i][0][zk] = min(dp[i][0][zk], dp[i - 1][1][kk] + (s[i] != 'R'));

						//i 人指右，i - 1 人指左
						if (zk != 2 && kk != 2)
							dp[i][1][zk] = min(dp[i][1][zk], dp[i - 1][0][kk] + (s[i] != 'L'));
					}
				}
			}

			//最后，我们的到的 n 结点状态要对应枚举的状态，这样才能保证有效性
			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. 简化组合情况。

参考博客

#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;
}
/*
*/