自动搬运

查看原文

来自洛谷，原作者为

	kara20 支持壶关，小号Nightbird回关（私信）||400粉爆照！！qwq||贴贴ElvinStarry，Bubbles~||珍惜当下||现5不拿7不改签

搬运于2025-08-24 21:42:14，当前版本为作者最后更新于2024-01-16 15:36:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

很明显这是一道 DP，首先我们先来分析一下这道题：

题目让我做什么：

穷举所有行走路线。

以什么为对象划分顺序，分几步完成，每一步做什么（决策）：

以步数划分顺序，分成 $H+G$ 步，决策是在 $H$ 序列走一步还是在 $G$ 序列走一步。

状态是什么，状态就是整个问题的描述：

这里不需要时间，因为时间一定等于 $i+j$（因为每一时刻肯定有一个人走一步），所以此时的状态就是 $f_{i,j}$,但是还有一个问题，就是如果这么写就没法算最后一步的花费。

现在的方程 $f_{i,j}$表示 $H$ 序列走到了 $i$，$G$ 序列走到了 $j$，此时我们最后一次访问（走到）的是 $H$ 序列还是 $G$ 序列我们不知道，所以就不能求最后一步的花费。

可以考虑往状态里增加一维，就是 $f_{i,j,0}$ 和 $f_{i,j,1}$。

• $f_{i,j,0}$ 表示 $H$ 序列的前 $i$ 个（访问）走完了，$G$ 序列的前 $j$ 个走完了，最后我们位于 $H$ 序列的最后一个位置。

• $f_{i,j,1}$ 就是最后我们位于 $G$ 序列的最后一个位置（前面一样后面改一下）。

状态转移方程：

我们来想一下最后的方程，有了方程就很好写代码啦，我觉得方程就是去掉最后一步的状态+最后一步的状态（大多数啊），想一想这两个状态上一步是由谁推出来的，先来看 $f_{i,j,0}$ 的方程,因为我们这里省略了一个 $x$ 时刻（若 $x=i+j$，则 $x$ 时刻状态为 $f_{i,j,0}$），那么我们想 $x-1$ 时刻状态是什么，是 $f_{i-1,j,0}$ 和 $f_{i-1,j,1}$（一个时刻只能走一步哦）然后再找到最后一步的状态，这两个方程的最后一步状态会用到 $dis$ 数组（感觉用这个会直观一点，当然你也可以用函数），$f_{i,j,1}$ 去掉最后一步的状态是：$f_{i,j-1,0}$ 和 $f_{i,j-1,1}$。

小知识：

ok，现在就差两个方程的最后一步状态了，我们需要知道一个原理，运用勾股定理可知：在平面直角坐标系中两个点的距离的平方 $=$ 两个点横坐标差的平方 $+$ 两个点纵坐标差的平方，所以这里我定义了 $3$ 个 $dis$ 数组，如下：

• $dis1$：$dis1$ 表示在 $H$ 序列里第 $i$ 个点和第 $i+1$ 个点距离的平方（也就是消耗的能量）。

dis1[i]=pow(H[i].x-H[i+1].x,2)+pow(H[i].y-H[i+1].y,2);

• $dis2$：$dis2$ 表示在 $H$ 序列里第 $i$ 个点和 $G$ 序列的第 $j$ 个点距离的平方（也就是消耗的能量）。

dis2[i][j]=pow(H[i].x-G[j].x,2)+pow(H[i].y-G[j].y,2);

• $dis3$：$dis3$ 表示在 $G$ 序列里第 $i$ 个点和第 $i+1$ 个点距离的平方（也就是消耗的能量）。

dis3[i]=pow(G[i].x-G[i+1].x,2)+pow(G[i].y-G[i+1].y,2);

现在我觉得方程你就能看懂啦ヾ(❀^ω^)ノﾞ。

f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+dis1[i-1],f[i-1][j][1]+dis2[i][j]));

f[i][j][1]=min(f[i][j][1],min(f[i][j-1][1]+dis3[j-1],f[i][j-1][0]+dis2[i][j]));

Code：

#include<bits/stdc++.h>//可爱的懒人头文件
using namespace std;
int n,m;
long long f[1009][1009][2],dis1[1009],dis3[1009],dis2[1009][1009];
struct node
{
    int x,y;
}H[1009],G[1009];//写一个结构体
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>H[i].x>>H[i].y;//读入H第i个点的坐标
    }
    for(int i=1;i<=m;i++)
    {
        cin>>G[i].x>>G[i].y;//读入G第i个点的坐标
    }
    for(int i=1;i<n;i++)
    {
        dis1[i]=pow(H[i].x-H[i+1].x,2)+pow(H[i].y-H[i+1].y,2);
    }
    for(int i=1;i<m;i++)
    {
        dis3[i]=pow(G[i].x-G[i+1].x,2)+pow(G[i].y-G[i+1].y,2);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dis2[i][j]=pow(H[i].x-G[j].x,2)+pow(H[i].y-G[j].y,2);

        }
    }
    memset(f,0x7f,sizeof(f));//初始化无穷大
    f[1][0][0]=0;//从题目可以看出农夫约翰最开始位于H序列的第一个点，所以第一维数组就是1，G序列一个点也没走所以第二维就是0，题目说农夫约翰在H结束所以第三维就是0
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+dis1[i-1],f[i-1][j][1]+dis2[i][j]));
            if(j>0)f[i][j][1]=min(f[i][j][1],min(f[i][j-1][1]+dis3[j-1],f[i][j-1][0]+dis2[i][j]));//DP方程
        }
    }
    cout<<f[n][m][0];
    return 0;
}