思路
题目只对向上走有限制，但是对左右走没有限制，所以可以将宝藏的位置按照行处理。
由于每个宝藏都要遍历到，记录每一行左右两个端点的宝藏。我猜了一个贪心就是每到一行从一个端点走到另一个端点路程最短，不能从中间往两边走。
所以按照每一行判断上一行的左端点到这一行的右端点，或左到左，右到左，右到右最短的长度，在加上当前行的长度，得到当前状态的最短长度，dp即可。
在有限制的情况下求两点的最短距离，就是如果两点中间隔着一条可以走的列，那么最短就是曼哈顿距离；否则就计算它们左右两边可以走的列的最短距离。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
#define endl '
'
#define inf 0x3f3f3f3f
const int M = 998244353;
ll l[N], r[N];
set<ll> posy;
vector<ll> col;
ll dis(ll x1, ll y1, ll x2, ll y2) {
auto p1 = lower_bound(col.begin(), col.end(), x1);
auto p2 = lower_bound(col.begin(), col.end(), x2);
if(p1 != p2) {
return abs(x1 - x2) + abs(y1 - y2);
} else if(p1 == col.begin()) {
ll tar = *p1;
return abs(x1 - tar) + abs(x2 - tar) + abs(y1 - y2);
} else if(p1 == col.end()) {
ll tar = *(p1 - 1);
return abs(x1 - tar) + abs(x2 - tar) + abs(y1 - y2);
} else {
ll tar1 = *p1;
ll tar2 = *(p1 - 1);
return min(abs(x1 - tar1) + abs(x2 - tar1),abs(x1 - tar2) + abs(x2 - tar2)) + abs(y1 - y2);
}
}
ll dp[N][10];
int main() {
ios::sync_with_stdio(false);
int n, m, k, q;
cin >> n >> m >> k >> q;
l[1] = r[1] = 1;
posy.insert(1);
for(int i = 0; i < k; i++) {
ll x, y;
cin >> y >> x;
if(!posy.count(y)) posy.insert(y);
l[y] = l[y] ? min(x, l[y]) : x;
r[y] = r[y] ? max(x, r[y]) : x;
}
for(int i = 0; i < q; i++) {
int c;
cin >> c;
col.push_back(c);
}
sort(col.begin(), col.end());
int cur = 2;
dp[1][0] = 2 * (r[1] - l[1]);
dp[1][1] = r[1] - l[1];
int lasty = 1;
for(auto y : posy) {
if(y == 1) continue;
dp[cur][0] += r[y] - l[y];
dp[cur][1] += r[y] - l[y];
dp[cur][0] += min(dp[cur - 1][0] + dis(l[lasty], lasty, r[y], y), dp[cur - 1][1] + dis(r[lasty], lasty, r[y], y));
dp[cur][1] += min(dp[cur - 1][0] + dis(l[lasty], lasty, l[y], y), dp[cur - 1][1] + dis(r[lasty], lasty, l[y], y));
cur++;
lasty = y;
}
cout << min(dp[cur - 1][0], dp[cur - 1][1]) << endl;
}