一个\(n*m\)的网格上有许多物品,一开始在(1,1),每次可以向左右走,仅在给定的几个列可以向上走,求取完所有物品的最短路程. \(n,m \leq 2*10^5\)

显然不适合最短路,原因在于每次到达一行必定要走完这一行的所有物品,而穿过物品不回头从另一端离开显然不一定是最优的.

考虑dp,容易发现,对于每层,只需要考虑取完该层物品之后从哪里去往下一层,而取完物品时一定位于物品块的两端,于是从每层物品块两端分别向下一层物品块的两端转移,对于每个转移,考虑依次尝试离四个端点的最近的两个通道,显然没有比这四个通道更优的方法(其他都是冤枉路),具体计算路程时还要考虑是否顺路完成了物品块的覆盖,以及是否需要走回头路.

细节较多,注意分类讨论:四端转移,每对有四种通道,每条路有四种通道与两端的相对位置,每种相对位置有左右端与左右端是否超过通道需要走回头路四种情况,共有\(4*4*4*4=64\)种情况,依次讨论即可.

注意几个坑点:

• 端点可能就在通道上,.不用找左右端直接尝试转移即可.
• 从某层往上可能都没有物品,要把它们删掉.
• 某两层间可能有多层没有物品,用指针记录上一个有物品的层即可.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int N = 200005, INF = 0x7ffffff;
int n, m, k, q;
bool treasure_in_line[N];
int left_of_line[N], right_of_line[N], safecolumn[N], closest_left_safe_column[N], closest_right_safe_column[N], len[N];
int dp[N][2];
namespace solve
{
    void init()
    {
        ios::sync_with_stdio(false);
        cin >> n >> m >> k >> q;
        for (int i = 1; i <= n; i++)
            left_of_line[i] = m + 1, right_of_line[i] = -1;
        for (int i = 1; i <= k; i++)
        {
            int x, y;
            cin >> x >> y;
            treasure_in_line[x] = 1;
            left_of_line[x] = min(left_of_line[x], y);
            right_of_line[x] = max(right_of_line[x], y);
        }
        for (int i = 1; i <= n; i++)
            len[i] = right_of_line[i] - left_of_line[i];
        for (int i = 1; i <= q; i++)
        {
            int temp;
            cin >> temp;
            safecolumn[temp] = 1;
        }
        for (int i = 1; i <= m; i++)
        {
            if (!safecolumn[i])
                continue;
            closest_left_safe_column[i] = i;
            closest_right_safe_column[i] = i;
            int templ = i - 1, tempr = i + 1;
            while (templ >= 1 && !safecolumn[templ])
            {

                closest_right_safe_column[templ] = i;
                templ--;
            }
            while (tempr <= m && !safecolumn[tempr])
            {

                closest_left_safe_column[tempr] = i;
                tempr++;
            }
        }
        int cnt = n;
        for (cnt; cnt >= 1; cnt--)
            if (treasure_in_line[cnt])
                break;
        if (cnt < n)
            n = cnt;
    }
    int real_distant(int line1, int line2, int column1, int column2, int path, int lr1, int lr2)
    {
        int sum;
        if (path <= column1 && path <= column2)
        {
            sum = column1 - path + column2 - path + 1;
            if (lr2 == 0)
                sum += 2 * len[line2];
            else
            {
                if (left_of_line[line2] < path)
                    sum += 2 * (path - left_of_line[line2]);
            }
        }
        if (path <= column1 && path >= column2)
        {
            sum = column1 - column2 + 1;
            if (lr2 == 1)
                sum += 2 * len[line2];
            else
            {
                if (right_of_line[line2] > path)
                    sum += 2 * (right_of_line[line2] - path);
            }
        }
        if (path >= column1 && path <= column2)
        {
            sum = column2 - column1 + 1;
            if (lr2 == 0)
                sum += 2 * len[line2];
            else
            {
                if (left_of_line[line2] < path)
                    sum += 2 * (path - left_of_line[line2]);
            }
        }
        if (path >= column1 && path >= column2)
        {
            sum = path - column1 + path - column2 + 1;
            if (lr2 == 1)
                sum += 2 * len[line2];
            else
            {
                if (right_of_line[line2] > path)
                    sum += 2 * (right_of_line[line2] - path);
            }
        }
        return sum;
    }
    int get_dis(int low_line, int high_line, int low_line_column, int high_line_column, int position_low, int position_high)
    {
        int ans = INF;
        if (closest_left_safe_column[low_line_column])
            ans = min(ans, real_distant(low_line, high_line, low_line_column, high_line_column, closest_left_safe_column[low_line_column], position_low, position_high));
        if (closest_right_safe_column[low_line_column])
            ans = min(ans, real_distant(low_line, high_line, low_line_column, high_line_column, closest_right_safe_column[low_line_column], position_low, position_high));
        if (closest_left_safe_column[high_line_column])
            ans = min(ans, real_distant(low_line, high_line, low_line_column, high_line_column, closest_left_safe_column[high_line_column], position_low, position_high));
        if (closest_right_safe_column[high_line_column])
            ans = min(ans, real_distant(low_line, high_line, low_line_column, high_line_column, closest_right_safe_column[high_line_column], position_low, position_high));
        return ans;
    }
}
using namespace solve;
int head=1;
signed main()
{
    init();
    if (!treasure_in_line[1])
    {
        dp[1][0] = 0, dp[1][1] = 0;
        left_of_line[1] = 1, right_of_line[1] = 1;
        len[1] = 0;
    }
    else
        dp[1][0] = left_of_line[1] - 1 + 2 * len[1], dp[1][1] = right_of_line[1] - 1;
    for (int i = 2; i <= n; i++)
        if (treasure_in_line[i])
        {
            dp[i][0] = i - head - 1 + min(dp[head][0] + get_dis(head, i, left_of_line[head], left_of_line[i], 0, 0), dp[head][1] + get_dis(head, i, right_of_line[head], left_of_line[i], 1, 0));
            dp[i][1] = i - head - 1 + min(dp[head][0] + get_dis(head, i, left_of_line[head], right_of_line[i], 0, 1), dp[head][1] + get_dis(head, i, right_of_line[head], right_of_line[i], 1, 1));
            head = i;
        }
    cout << min(dp[n][0], dp[n][1]);
}