P2848 [USACO16DEC] Cow Checklist G 题解

· · 题解

思路：

很明显这是一道 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} 的方程,因为我们这里省略了一个 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[i]=pow(H[i].x-H[i+1].x,2)+pow(H[i].y-H[i+1].y,2);
dis2[i][j]=pow(H[i].x-G[j].x,2)+pow(H[i].y-G[j].y,2);
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;
}