[洛谷 2848][USACO16DEC]Cow Checklist

题目链接

https://www.luogu.org/problem/P2848

题解

不算太难的 DP 题。

我们设 \(f(i,j,0/1)\) 表示访问前 \(i\) 头 H 种奶牛，前 \(j\) 头 G 奶牛，且当前位于 H 种奶牛 / G 种奶牛时的最小花费。

边界为 \(f(1,0,0)=0\)，其余为 INF。

转移的时候枚举 \(i,j\) 的值，每一步有两种决策：

1. 访问下一头 H 种奶牛；
2. 访问下一头 G 种奶牛。

根据题意转移即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct point
{
 int x,y;
}p1[1005],p2[1005];
long long f[1005][1005][2];
int calc(int x1,int y1,int x2,int y2)
{
 return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int main()
{
 int h,g;
 scanf("%d%d",&h,&g);
 for(int i=1;i<=h;i++)
  scanf("%d%d",&p1[i].x,&p1[i].y);
 for(int i=1;i<=g;i++)
  scanf("%d%d",&p2[i].x,&p2[i].y);
 memset(f,INF,sizeof(f));
 f[1][0][0]=0;
 for(int i=1;i<h;i++)
  for(int j=0;j<=g;j++)
  {
   f[i+1][j][0]=min(f[i+1][j][0],
                    min(f[i][j][1]+calc(p1[i+1].x,p1[i+1].y,p2[j].x,p2[j].y),
                        f[i][j][0]+calc(p1[i+1].x,p1[i+1].y,p1[i].x,p1[i].y)));
   if(j<g)
    f[i][j+1][1]=min(f[i][j+1][1],
                     min(f[i][j][1]+calc(p2[j+1].x,p2[j+1].y,p2[j].x,p2[j].y),
                         f[i][j][0]+calc(p2[j+1].x,p2[j+1].y,p1[i].x,p1[i].y)));
  }
 printf("%d\n",int(f[h][g][0]));
 return 0;
}