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 + ;

typedef long long ll;

int Max[maxn], Min[maxn], num[maxn], cnt;

ll dp[maxn][];

ll dis(int x,int y)

{

    int l = *(lower_bound(num + , num +  + cnt, x));

    int r = *(upper_bound(num + , num +  + cnt, x) - );

    return min(abs(x - l) + abs(y - l), abs(x - r) + abs(y - r));

}

int main()

{

    int n, m, k, q, ans = ;

    scanf("%d%d%d%d", &n, &m, &k, &q);

    memset(Min, inf, sizeof(Min));

    for(int i=;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=;i<=q;i++)

    {

        int x;

        scanf("%d", &x);

        num[i] = x;

    }

    cnt = q;

    num[++cnt] = inf; num[++cnt] = -inf;

    sort(num + , num +  + cnt);

    if(Max[]==) Max[] = , Min[] = ;

    dp[][] = Max[] *  - Min[] - ;

    dp[][] = Max[] - ;

    //printf("ww  %lld %lld\n", dp[1][0], dp[1][1]);

    int x = ;

    for(int i=;i<=n;i++)

    {

        //printf("i=%d\n", i);

        if (Max[i] == ) continue;

        dp[i][] = min(dis(Min[x], Max[i]) + dp[x][], dis(Max[x], Max[i]) + dp[x][]);

        dp[i][] = min(dis(Min[x], Min[i]) + dp[x][], dis(Max[x], Min[i]) + dp[x][]);

        //printf("dp[%d][0]=%lld dp[%d][1]=%lld\n", i, dp[i][0], i, dp[i][1]);

        dp[i][] += abs(Max[i] - Min[i]) + i - x;

        dp[i][] += abs(Max[i] - Min[i]) + i - x;

        x = i;

        //printf("dp[%d][0]=%lld dp[%d][1]=%lld\n", i, dp[i][0], i, dp[i][1]);

    }

    //printf("ans=%d\n", ans);

    printf("%lld\n", min(dp[ans][], dp[ans][]));

    return ;

}

巴特西

Codeforces Round #577 (Div. 2) D. Treasure Hunting

最新文章

热门文章