\(2000\) 分的 DP 题。
题意
给定一个 \(2\) 行 \(n\) 列的网格。机器人初始坐标为 \((0,1)\)，每一秒都可以向四周移动。每个格子有解锁时间，在该时间之前机器人不可以进入该格子。每个网格只可以遍历一遍，求机器人遍历整个网格图的最少时间。\(n\leq2*10^5\)。
思路
显然，由于每个网格只能遍历一遍，机器人只有两种走法：
1.从当前格子一直向右行走，到达第 \(n\) 列拐弯，再一直向左移动；
2.蛇形走法。
一开始的思路，状态设计成了 \(f_{i,j,k}\) 表示当前要向 \(k\) 方向走到 \((i,j)\) 的最小时间。发现当方向为向左时，状态要从 \(f_{i,j+1,k}\) 转移而来，有后效性。
再次思考性质，发现我们并没有必要走到一个格子后再停下来，等待它的解锁时间。我们可以直接计算好这一条路径所需要等待的总时间，结果便是等待的时间加上格子数了。
该怎么实现呢？观察到蛇形走法的结果可以边走边由直线走法的结果推算出来，于是考虑对直线走法的结果进行预处理。设 \(f_{i,j}\) 表示从 \((i,j)\) 开始，要向右边移动的最小等待时间。
如何转移？在不考虑不同行之间的情况时，显然可以得到：
\(f_{i,j}=max(f_{i,j+1}-1,a_{i,j})\)。
加上不同行的情况，即蛇形走法后怎么办呢？考虑到如果从 \((i,j)\) 开始向右移动，终点一定是 \((i\oplus1,j)\)。显然答案要从终点转移过来。故转移方程变为：
\(f_{i,j}=max(f_{i,j+1}-1,max(a_{i\oplus1,j}-2*(n-j)-1,a_{i,j}))\)。
转移方程是怎么来的呢？有的小朋友就有疑问了。\((i,j)\) 走到 \((i\oplus1,j)\) 的路径，不是等同于由 \((i,j)\) 走到 \((i,n)\)，再拐个弯走到 \((i\oplus1,j)\) 吗？那这样的路径显然可以用 \((i,j+1)\) 的状态来转移啊，为什么非要从终点转移过来呢？因为你忘记考虑时间锁的限制了。\((i,j+1)\) 的时间锁和 \((i\oplus1,j)\) 的时间锁不一定相同，所以如果两种情况用同一种状态转移的话，答案是错误的。故需要用 \((i\oplus1,j)\) 的时间锁限制减去机器人移动 \((n-j)\) 列所需的时间，再减去拐弯所需的 \(1\) 个时间作为转移状态。
最后，枚举一下蛇形走法的路径，统计一下最小值就可以了。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
int T=1,n,a[2][200010],f[2][200010],ans,now;
void solve(){
cin>>n;
for(int i=0;i<=1;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
a[0][1]=-1;
f[0][n]=max(a[1][n]-1,a[0][n]);
f[1][n]=max(a[0][n]-1,a[1][n]);
for(int i=0;i<=1;i++){
for(int j=n-1;j>=1;j--){
f[i][j]=max(f[i][j+1]-1,max(a[i^1][j]-2*(n-j)-1,a[i][j]));
}
}
ans=f[0][1]+2*n,now=a[1][1]+1;
for(int i=2,p=1;i<=n;i++,p^=1){
ans=min(ans,now+((f[p][i]-now)>0?f[p][i]-now:0)+2*(n-i+1));
now=max(now+1,a[p][i]+1);
now=max(now+1,a[p^1][i]+1);
}
cout<<min(ans,now)<<endl;
for(int i=1;i<=n;i++) f[0][i]=f[1][i]=0;
return ;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>T;
while(T--){
solve();
}
return 0;
}