Codeforces Round #577 (Div. 2) D. Treasure Hunting
这个一场div2 前面三题特别简单，这个D题的dp还是比较难的，不过题目告诉你了只能往上走，所以还是可以看出来这个是一个dp的。
然后对于每一段，肯定是从左到右或者从右到左这个是最优的，这里就是有一点点贪心的思想。
所以要我们首先要求出每一行的最大最小，然后就是开始转移。
题目要求只有一部分的列才可以竖直方向的走，这个让我就有点迷糊。
首先每一段向下转移，如果这个位置向下转移到的那个位置直接有直线可以竖着的走，
那么可以知道这个肯定是最优的，如果没有就只能找两边的了。
这个其实有点难写，看了别人的代码发现，这个可以用lower_bound 和 upper_bound 很巧妙的解决。
首先在一个数组里面存下可以走的每一列，然后还要存一个最小值-inf，和一个最大值 inf。然后排序一下。
然后就是找对于每一个区间，就是刚刚说的那个转移区间，(x,y) 注意 x不一定小于等于y
我们开始用lower_bound 找到大于等于x的最大值，如果没有大于等于x的那么就会找到inf，这个很自然会被舍去，然后upper_bound 就会找到区间左边的，
如果找到了大于等于的，那么用upper_bound会找到相同的位置，然后-1就是区间左边的，这个时候就判断一下，选哪个更优。
如果y>y 也是一样的，这个lower_bound 会找到两边的，如果中间有那么upper_bound也会找到。
这个之后还要加一点点东西，竖直距离和max[i]-min[i]
#include <cstring> #include <queue> #include <cstdlib> #include <cstdio> #include <iostream> #include <algorithm> #include <map> #include <vector> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 2e5 + 10; typedef long long ll; int Max[maxn], Min[maxn], num[maxn], cnt; ll dp[maxn][2]; ll dis(int x,int y) { int l = *(lower_bound(num + 1, num + 1 + cnt, x)); int r = *(upper_bound(num + 1, num + 1 + cnt, x) - 1); return min(abs(x - l) + abs(y - l), abs(x - r) + abs(y - r)); } int main() { int n, m, k, q, ans = 0; scanf("%d%d%d%d", &n, &m, &k, &q); memset(Min, inf, sizeof(Min)); for(int i=1;i<=k;i++) { int l, r; scanf("%d%d", &l, &r); Max[l] = max(Max[l], r); Min[l] = min(Min[l], r); ans = max(ans, l); } for(int i=1;i<=q;i++) { int x; scanf("%d", &x); num[i] = x; } cnt = q; num[++cnt] = inf; num[++cnt] = -inf; sort(num + 1, num + 1 + cnt); if(Max[1]==0) Max[1] = 1, Min[1] = 1; dp[1][0] = Max[1] * 2 - Min[1] - 1; dp[1][1] = Max[1] - 1; //printf("ww %lld %lld ", dp[1][0], dp[1][1]); int x = 1; for(int i=2;i<=n;i++) { //printf("i=%d ", i); if (Max[i] == 0) continue; dp[i][0] = min(dis(Min[x], Max[i]) + dp[x][0], dis(Max[x], Max[i]) + dp[x][1]); dp[i][1] = min(dis(Min[x], Min[i]) + dp[x][0], dis(Max[x], Min[i]) + dp[x][1]); //printf("dp[%d][0]=%lld dp[%d][1]=%lld ", i, dp[i][0], i, dp[i][1]); dp[i][0] += abs(Max[i] - Min[i]) + i - x; dp[i][1] += abs(Max[i] - Min[i]) + i - x; x = i; //printf("dp[%d][0]=%lld dp[%d][1]=%lld ", i, dp[i][0], i, dp[i][1]); } //printf("ans=%d ", ans); printf("%lld ", min(dp[ans][0], dp[ans][1])); return 0; }