#C241114D. 圆环型零件

标签（Label）

动态规划
分类讨论

网址（Website）

F - Hands on Ring (Hard) (atcoder.jp)

[ABC376F] Hands on Ring (Hard) - 洛谷

题目（Problem）

问题陈述

你正用双手拿着一个戒指。这个戒指由编号为 $1,2,\dots,N$ 的 $N\ (N \geq 3)$ 部分组成，其中 $i$ 和 $i+1$（$1 \leq i \leq N-1$）部分相邻，$1$ 和 $N$ 部分也相邻。

最初，您的左手拿着部件 $1$，右手拿着部件 $2$。在一次操作中，您可以完成以下操作：

将其中一只手移动到当前所持部件的相邻部分。但是，只有当另一只手不在目标部件上时才能这样做。

下图显示了初始状态以及可以和不可以进行的操作示例。写在圆环各部分上的数字代表零件编号，标有 L 和 R 的圆圈分别代表你的左手和右手。

你需要按照 $Q$ 的指示依次进行。第 $i$ 次（$1 \leq i \leq Q$）指令由字符 $H_i$ 和整数 $T_i$ 表示，意思如下：

执行一定数量的操作（可能为零），使您的左手（如果 $H_i$ 为 L）或右手（如果 $H_i$ 为 R）拿着 $T_i$。在此，您可以动 $H_i$ 未指定的另一只手。

求执行所有指令所需的最小操作总数。

限制因素

$3\leq N \leq 3000$
$1\leq Q \leq 3000$
$H_i$ 是 “L” 或 “R”。
$1 \leq T_i \leq N$
$N$ 、 $Q$ 和 $T_i$ 是整数。

输入格式

输入内容由标准输入法提供，格式如下：

$N$ $Q$
$H_1$ $T_1$
$H_2$ $T_2$
$\vdots$
$H_Q$ $T_Q$

输出格式

打印遵循所有指令所需的最小操作总数。

样例 #1

样例输入 #1

样例输出 #1

通过以下操作，您可以按顺序执行所有 $Q$ 指令。

移动右手作为 $2 \rightarrow 3 \rightarrow 4$ 的一部分，执行第一条指令。
移动左手作为 $1 \rightarrow 6 \rightarrow 5$ 部分，执行第二条指令。
移动左手作为 $5 \rightarrow 6$ 部分，然后移动右手作为 $4 \rightarrow 5$ 部分，执行第三个指令。

在这种情况下，总操作次数为 $2+2+1+1=6$ ，是最少的。

样例 #2

样例输入 #2

100 2
L 1
R 2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

题解（Solution）

$\qquad$转移倒是比较简单，主要就是没有往 $\text{dp}$ 方面想，导致最后没有做出来。

$\qquad$这道题还有一个非常优秀的维度优化，其实也比较好想。可以去洛谷看看这道题。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first 
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5005;
bool ST;

int n,q,ans;

int f[N][N];

inline P calc1(int x,int y,int to){
	int dis=0;
	if(y<x) y+=n;
	if(to<x) to+=n;
	if(y>to){
		dis+=to-x;
		return {y%n, dis};
	}
	dis+=to-x+to+1-y, y=to+1;
	return {y%n, dis};
}

inline P calc2(int x,int y,int to){
	auto res = calc1(n-x-1, n-y-1, n-to-1);
	return {n-res.x-1, res.y};
}

void Solve(){
	memset(f, 0x3f, sizeof f), f[0][1] = 0;
	cin>>n>>q;
	for(int i=1,op=0,lx=0;i<=q;i++){
		char c;cin>>c;
		int to=rd()-1;
		int h=c=='R';
		For(j,0,n-1){
			int p1=lx, p2=j;
			if(op^h) swap(p1,p2);
			P res = calc1(p1,p2,to);
			f[i][res.x] = min(f[i][res.x], f[i-1][j]+res.y);
			res = calc2(p1,p2,to);
			f[i][res.x] = min(f[i][res.x], f[i-1][j]+res.y);
		}
		op = h, lx = to;
	}cout<<*min_element(f[q],f[q]+n)<<'\n';
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}