ABC-376-F-Hands on Ring (Hard) · znzryb
## 题目大意
有一个环形的 $n$ 个点（编号 $1sim n$），两只手初始在固定位置。给出 $m$ 次操作，每次要求移动某一只手到指定点，移动代价为沿环走的最短步数，同时两只手不能占用同一个点（或有重叠限制）。求完成所有操作的最小总代价。
## AC代码
其实与B题的唯一不同点就是你可以动另一只手。
这题让我想起来天津省选的线段
[https://www.luogu.com.cn/problem/P3842](https://www.luogu.com.cn/problem/P3842)
[AC记录](https://www.luogu.com.cn/record/176665084)
这个线段就是你要忽略一些其实没有意义的情况，这道题应该也是一样，你不必把两只手在哪个点都存下来，因为后走和前走是一样的
**注意防重叠条件的书写**
就是我之前写`if(pos≠j)` 但实际上j有可能代表副手，也有可能代表主手，如果代表副手就有问题了，pos就是移动副手，副手不应该和副手重叠？搞笑
其实可以在cal函数中写这个逻辑，但因为这个cal函数是从B题拉过来的，我就懒得改了
分享一组hack数据
```
8 7
L 2
L 3
L 4
L 5
L 6
L 7
L 8
```
应输出
```
14
```
AC [https://atcoder.jp/contests/abc376/submissions/59140626](https://atcoder.jp/contests/abc376/submissions/59140626)
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
}
ll cal(char op,ll L,ll R,ll obj) { // 计算并返回需要走几步
ll res=0;
if(op=='L') {
ll zhenMove=abs(L-obj);
ll fanMove=n-zhenMove;
if(obj<L) {
if(R<L && R>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(R>L && R<obj)
res+=fanMove;
else
res+=zhenMove;
}
}else {
ll zhenMove=abs(R-obj);
ll fanMove=n-zhenMove;
if(obj<R) {
if(L<R && L>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(L>R && L<obj)
res+=fanMove;
else
res+=zhenMove;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int opup=0;
memset(dp,0x3f,sizeof(dp));
ll inf = dp[0][0];
dp[0][2]=0; // 此时r在2
ll opupObj=1; // 假装有一个0号命令 让L走到 1
for(int i=1;i<=m;i++) {
cin>>oper>>object;
int op= oper=='L'? 0:1;
for(int j=1;j<=n;j++) {
if(dp[i-1][j]==inf)
continue;
if(op==opup && op==0) { // 此时 j 即为right手 opuploc 即为 left dp里应该存的仍然是r手
// r手可自由移动
ll l=opupObj,r=j;
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
if(pos!=l)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=l)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}else if(op==opup && op==1) {
// l手可自由移动
ll l=j,r=opupObj;
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
if(pos!=r)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=r)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==1 && opup==0) {
ll l=opupObj,r=j; // 可以随便动的手是left 要动的手是right
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
if(pos!=r)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=r)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==0 && opup==1) {
ll l=j,r=opupObj; // 可以随便动的手是right 要动的手是left
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
if(pos!=l)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=l)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}
}
opup=op;opupObj=object;
}
ll ans=inf;
for(int i=1;i<=n;i++) {
ans=min(ans,dp[m][i]);
}
cout<<ans<<endl;
// debug();
}
// AC https://atcoder.jp/contests/abc376/submissions/59140626
```
## 心路历程（WA，TLE，MLE……）
WA了13个点
[https://atcoder.jp/contests/abc376/submissions/59134285](https://atcoder.jp/contests/abc376/submissions/59134285)
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
}
ll cal(char op,ll L,ll R,ll obj) { // 计算并返回需要走几步
ll res=0;
if(op=='L') {
ll zhenMove=abs(L-obj);
ll fanMove=n-zhenMove;
if(obj<L) {
if(R<L && R>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(R>L && R<obj)
res+=fanMove;
else
res+=zhenMove;
}
}else {
ll zhenMove=abs(R-obj);
ll fanMove=n-zhenMove;
if(obj<R) {
if(L<R && L>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(L>R && L<obj)
res+=fanMove;
else
res+=zhenMove;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int opup=0;
memset(dp,0x3f,sizeof(dp));
ll inf = dp[0][0];
dp[0][2]=0; // 此时r在2
ll opupObj=1; // 假装有一个0号命令 让L走到 1
for(int i=1;i<=m;i++) {
cin>>oper>>object;
int op= oper=='L'? 0:1;
for(int j=1;j<=n;j++) {
if(dp[i-1][j]==inf)
continue;
if(op==opup && op==0) { // 此时 j 即为right手 opuploc 即为 left dp里应该存的仍然是r手
// r手可自由移动
ll l=opupObj,r=j;
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}else if(op==opup && op==1) {
// l手可自由移动
ll l=j,r=opupObj;
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==1 && opup==0) {
ll l=opupObj,r=j; // 可以随便动的手是left 要动的手是right
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==0 && opup==1) {
ll l=j,r=opupObj; // 可以随便动的手是right 要动的手是left
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}
}
opup=op;opupObj=object;
}
ll ans=inf;
for(int i=1;i<=n;i++) {
ans=min(ans,dp[m][i]);
}
cout<<ans<<endl;
//debug();
}
```
[](https://atcoder.jp/contests/abc376/submissions/59136104)
WA了9个点，解决了一些特殊情况
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
}
ll cal(char op,ll L,ll R,ll obj) { // 计算并返回需要走几步
ll res=0;
if(op=='L') {
ll zhenMove=abs(L-obj);
ll fanMove=n-zhenMove;
if(obj<L) {
if(R<L && R>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(R>L && R<obj)
res+=fanMove;
else
res+=zhenMove;
}
}else {
ll zhenMove=abs(R-obj);
ll fanMove=n-zhenMove;
if(obj<R) {
if(L<R && L>obj)
res+=fanMove;
else
res+=zhenMove;
}else {
if(L>R && L<obj)
res+=fanMove;
else
res+=zhenMove;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int opup=0;
memset(dp,0x3f,sizeof(dp));
ll inf = dp[0][0];
dp[0][2]=0; // 此时r在2
ll opupObj=1; // 假装有一个0号命令 让L走到 1
for(int i=1;i<=m;i++) {
cin>>oper>>object;
int op= oper=='L'? 0:1;
for(int j=1;j<=n;j++) {
if(dp[i-1][j]==inf)
continue;
if(op==opup && op==0) { // 此时 j 即为right手 opuploc 即为 left dp里应该存的仍然是r手
// r手可自由移动
ll l=opupObj,r=j;
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}else if(op==opup && op==1) {
// l手可自由移动
ll l=j,r=opupObj;
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==1 && opup==0) {
ll l=opupObj,r=j; // 可以随便动的手是left 要动的手是right
ll pos= object%n+1;
if(l!=object)
dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
}else if(op==0 && opup==1) {
ll l=j,r=opupObj; // 可以随便动的手是right 要动的手是left
ll pos= object%n+1;
if(r!=object)
dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
pos= object==1 ? n:object-1;
if(pos!=j)
dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
}
}
opup=op;opupObj=object;
}
ll ans=inf;
for(int i=1;i<=n;i++) {
ans=min(ans,dp[m][i]);
}
cout<<ans<<endl;
//debug();
}
```