4.1201D - Treasure Hunting
题目意思：
在一个n*m的地图上面，左下角的坐标是（1,1），最开始你位于左下角，一秒钟你可以进行往左或者往右的操作，你只能在一些特殊的列上面进行往上移动的操作，你不可以往下移动。现在告诉你k个宝藏的坐标信息以及哪些列是允许往上的，问最后至少要几秒可以遍历k个宝藏。
思路：
原先的思路：
所有的数据大小都是2e5，因为永远不可以往下操作，所以一定是把靠下的行里面的宝藏都处理完了之后才会往上，对于每一行的宝藏，最终一定是停留在最左边或者最右边，不可能有例外，也就是如果说一行里面存在宝藏，只关心最左边和最右边的列的信息就可以了。原先的想法是对于最左边，可能有两种可能，第一种是最后在这个宝藏最靠近的左边的特殊的列结束，第二种是右边的最近的特殊的列，最右边的点也有上面这两种，然后对于新的一行也是有4种，那么转移方程大概就是4*4=16块。那么是可以用DP来解决的，用数组存储每一行的四种状态然后去逐渐递推出下一行的四种状态。但是码量着实不小。。。。。想到这里就开始看题解了。
用dp[i] [0]表示在第i行处理完宝藏之后最后在最左边的宝藏的位置所用的最小花费
dp[i] [1] 表示处理完之后再这一行最右边的宝藏的位置
上面的思路是最后一定要在安全的列，但是其实可以不用这么麻烦，可以只讨论到达宝藏的情况，之后在第i行怎么到了第i+1行，以及需不需要到达第i+1行，都留给之后进行判断。
具体是怎么判断的呢？
看转移方程：对于dp[i+1] [0] 的推理：也就是现在想要处理完第i+1行之后处于最左边的宝藏。
dp[i+1][0]=min(dp[i][0]+dis(l[i],r[i+1]),dp[i][1]+dis(r[i],r[i+1]))+r[i+1]-l[i+1];
//解读一下，最后想要位于最左边，但是所有的宝藏都是需要遍历的。所以花费应该是从现在的位置先到达最右边再加上整个这一行宝藏的跨度。
//这一点可以记住。之后如果遇到类似的要遍历的情况，假如说最后想要留在最左边，就先求出来如何到达最右边，再加上整个跨度。
min函数里面有两部分，第一部分是由当前这一行的最左边到达下一行的最右边，第二部分是从当前的最右边到达下一行的最右边。dis函数就是从一个宝藏的位置到达另外一个宝藏的位置，但是必须是第一个数先到达一个特殊的列，再由第二个点到达一个特殊的列。这里的具体代码这样写：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,k,q;
int l[N],r[N],f[N],pr[N],nx[N];
//pr是这个列最近的前面的也就是<=的。
//nx是后面的
int dp[N][2];
int dis(int x,int y){
if(x>y) swap(x,y);
if(pr[y]>=x) return y-x;
int res=0x3f3f3f3f3f3f3f3f;
if(nx[y]) res=min(res,nx[y]-y+nx[y]-x);
if(pr[x]) res=min(res,x-pr[x]+y-pr[x]);
return res;
}
signed main()
{
cin>>n>>m>>k>>q;
n=m=0;
for(int i=1;i<=k;i++){
int x,y; cin>>x>>y;
n=max(n,x); m=max(y,m);
l[x]=l[x]==0?y:min(l[x],y);
r[x]=r[x]==0?y:max(r[x],y);
}
for(int i=1;i<=q;i++){
int x; cin>>x;
m=max(m,x);
f[x]=1;
}
for(int i=1;i<=m;i++){
pr[i]=f[i]?i:pr[i-1];
}
for(int i=m;i>=1;i--){
nx[i]=f[i]?i:nx[i+1];
}
if(l[1]==0) l[1]=r[1]=1;
dp[1][0]=r[1]-1+r[1]-l[1];
dp[1][1]=r[1]-1;
for(int i=2;i<=n;i++){
if(l[i]==0){
l[i]=l[i-1],r[i]=r[i-1];
dp[i][0]=dp[i-1][0]; dp[i][1]=dp[i-1][1];
continue;
}
else{
dp[i][0]=min(dp[i-1][0]+dis(l[i-1],r[i]),dp[i-1][1]+dis(r[i-1],r[i]))+r[i]-l[i];
dp[i][1]=min(dp[i-1][0]+dis(l[i-1],l[i]),dp[i-1][1]+dis(r[i-1],l[i]))+r[i]-l[i];
}
}
int ans=min(dp[n][0],dp[n][1])+n-1;
cout<<ans<<endl;
return 0;
}
int dis(int x, int y)
{
int res = INF;
int qr = upper_bound(sf + 1, sf + 1 + q, x) - sf;
int ql = qr - 1;
if(ql > 0) res = min(res, abs(x - sf[ql]) + abs(y - sf[ql]));
if(qr <= q) res = min(res, abs(x - sf[qr]) + abs(y - sf[qr]));
return res;
}
————————————————
版权声明：本文为CSDN博主「Sankkl1」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Sankkl1/article/details/121343575
//对于dis函数的解释：
/*
dis(int a,int b) 两个参数的含义：原先在a位置，然后需要通过一些安全的列到达b位置，问最小的花费。
竖直方向上面的，在程序最后面用了整体处理的方法处理了，所以现在我们只考虑水平方向。
按理说是要从下一行到达上一行，但是如果我们是处理上一行到达下一行的这个位置的水平的花费的话，最后得到的结果都是一样的，所以并不需要在意a,b究竟是谁。所以可以强制a<b 方便处理。
三种情况：当a b 之间有一个安全的列的话，从a到b是可以直接过来的，也就是直接return b-a
上述情况不可以的话，用只剩两种情况：b后面有安全的列，a前面有安全的列，两种情况都遍历一下，然后找最优化的。
对于b后面的，我们只需要知道距离b最近的后面的就可以了，同理，对于a前面的，也只需要知道最靠近a前面的。
所以我们用了pr nx数组来实现这个功能。
用二分寻找最近的也是可以的。
*/
代码上感觉还是很巧妙的，不过是借鉴其他人的。
用了l[] r[] 数组来记录每一行如果有宝藏的话的最左边、最右边。
列的范围最大之后2e5，先用f数组记录当前列是不是安全的，然后遍历就可以得到每一个列的最靠近的前面的安全的列，以及后面的最靠近的安全的列。