1392D. Omkar and Bed Wars(状态略复杂的dp)

$决策之间相互影响,dp比较好解决这类问题$

$但是1和n是特殊的元素,1和n相邻,考虑起来很麻烦$

$所以直接把1和n定义到状态里去$

$定义dp[i][j][q][k]为前i-1个人符合条件$

$且1号往j方向打人,n号往q方向打人,当前位置往k方向打人$

但这么设计状态是有问题的,有后效性

我们知道一个位置不合法当且仅当前面,自己,后面打人的方向一致

也就是自己只被一个人打,而且自己没有打他,这是不合法的

而对于当前状态,根本没记录被几个人打

后一个人转移的时候无法判断前一个位置是否合法

正确的状态还要加一维自己被打的信息

$dp[i][j][q][k][w]定义前i-1个位置合法$

$1号往j打,n号往q打,自己往k打,w表示$是否被上一个人打

这样转移就很方便

$举个例子,dp[3][0][1][0][0]的含义是(0表示左,1表示右)$

$前2个位置合法,1号往左打,n号往右打,自己往左打,且自己没有被左边打$

$那么此时转移是$

$$dp[3][0][1][0][0]=dp[2][0][1][0][1]$$

$由于3号没被2号打,那么2号一定是往左打$

$且二号一定被左边的人打$

$如果不被左边的人打,就出现矛盾.因为此时2号只被3号打却没有打3号$

当然还有一些初始化细节,看代码吧,不懂可以评论区提问8

(如果你有更好的写法,也可以和我分享一下…)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,t,dp[maxn][2][2][2][2];
char a[maxn],b[maxn];
int main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n;
		cin >> (a+1);
		//dp[i][j][q][k][s] 前i满足且1,n分别往j,q方向打人,s表示是否被左边打
		for(int i=1;i<=n;i++)
		for(int j=0;j<=1;j++)
		for(int q=0;q<=1;q++)
		for(int k=0;k<=1;k++)
		for(int w=0;w<=1;w++)
			dp[i][j][q][k][w]=1e9; 
		//下面是初始化 
		dp[1][0][0][0][0]=( a[1]!='L' )+( a[n]!='L');
		dp[1][0][1][0][1]=( a[1]!='L' )+( a[n]!='R');
		dp[1][1][0][1][0]=( a[1]!='R' )+( a[n]!='L');
		dp[1][1][1][1][1]=( a[1]!='R' )+( a[n]!='R');
		for(int i=2;i<n;i++)
		for(int j=0;j<=1;j++)
		for(int q=0;q<=1;q++)
		{
			int s=1;
			if( a[i]=='L' )//往左边打 
			{
				dp[i][j][q][0][0]=dp[i-1][j][q][0][1];//一定被左边打 
				dp[i][j][q][0][1]=min(dp[i-1][j][q][1][0],dp[i-1][j][q][1][1] );
				dp[i][j][q][1][0]=min(dp[i-1][j][q][0][0],dp[i-1][j][q][0][1])+s;
				dp[i][j][q][1][1]=dp[i-1][j][q][1][0]+s;
			}
			else
			{
				dp[i][j][q][0][0]=dp[i-1][j][q][0][1]+s;
				dp[i][j][q][0][1]=min(dp[i-1][j][q][1][0],dp[i-1][j][q][1][1] )+s;
				dp[i][j][q][1][0]=min(dp[i-1][j][q][0][0],dp[i-1][j][q][0][1]);
				dp[i][j][q][1][1]=dp[i-1][j][q][1][0];
			}
		}
		int ans=1e9;
		for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
		for(int k=0;k<=1;k++)
		{
			if( i==0&&j==0&&k==0)//n只被1个人打却没有还手,不合法 
				continue;
			if( i==1&&j==1&&k==1 )//n只被1个人打却没有还手,不合法 
				continue;
			if( !(j==0&&k==0) )//除去n-1位置不合法的情况 
				ans=min(ans,dp[n-1][i][j][k][0]);//n-1不被左边打 
			if( !(j==1&&k==1) )//除去n-1位置不合法的情况 
				ans=min(ans,dp[n-1][i][j][k][1]);//n-1被左边打 
		}
		cout << ans << endl;
	}
}