P2848 [USACO16DEC] Cow Checklist G
题目描述
每天，Farmer John 都会穿过他的牧场，检查每头奶牛的健康状况。他的农场里有两类奶牛：荷斯坦牛和根西牛。他的HHH头荷斯坦牛被方便地编号为1…H1 \ldots H1…H，而他的GGG头根西牛被方便地编号为1…G1 \ldots G1…G（1≤H≤1000,1≤G≤10001 \leq H \leq 1000, 1 \leq G \leq 10001≤H≤1000,1≤G≤1000）。每头奶牛都位于二维平面中的一个点（不一定不同）。
Farmer John 从荷斯坦牛111开始他的巡视，并在荷斯坦牛HHH结束。他希望沿途访问每头奶牛，并且为了方便维护他已经访问过的奶牛清单，他希望按照编号顺序访问荷斯坦牛和根西牛。在他访问的所有H+GH+GH+G头奶牛的序列中，编号为1…H1 \ldots H1…H的荷斯坦牛应作为一个（不一定连续的）子序列出现，同样地，编号为1…G1 \ldots G1…G的根西牛也应如此。换句话说，所有H+GH+GH+G头奶牛的序列应通过将编号为1…H1 \ldots H1…H的荷斯坦牛列表与编号为1…G1 \ldots G1…G的根西牛列表交错排列而成。
当 Farmer John 从一头奶牛移动到另一头奶牛，移动距离为DDD时，他会消耗D2D^2D2的能量。请帮助他确定按照上述巡视方式访问所有奶牛所需的最小能量。
输入格式
输入的第一行包含用空格分隔的HHH和GGG。
接下来的HHH行包含HHH头荷斯坦牛的xxx和yyy坐标，随后的GGG行包含根西牛的坐标。每个坐标都是0…10000 \ldots 10000…1000范围内的整数。
输出格式
输出一行，表示 Farmer John 巡视所有奶牛所需的最小能量。
输入输出样例 #1
输入 #1
3 2 0 0 1 0 2 0 0 3 1 3输出 #1
20C++实现
#include<bits/stdc++.h>//可爱的懒人头文件usingnamespacestd;intn,m;longlongf[1009][1009][2],dis1[1009],dis3[1009],dis2[1009][1009];structnode{intx,y;}H[1009],G[1009];//写一个结构体intmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>H[i].x>>H[i].y;//读入H第i个点的坐标}for(inti=1;i<=m;i++){cin>>G[i].x>>G[i].y;//读入G第i个点的坐标}for(inti=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(inti=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(inti=1;i<=n;i++){for(intj=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;for(inti=1;i<=n;i++){for(intj=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];return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
