大家好！我是小码匠。
昨天下午继续刷题，老码农管用的伎俩，给我找了4道题，自己从中选题做。
作为一个爱躺平的咸鱼，一眼相中了这道题：P2848 [USACO16DEC] Cow Checklist G
我瞄了一眼评论区，看有人要求：建议评黄, 现在是：提高 /省选，估计这题就不难，就它了，是我喜欢的菜。
题目：P2848 [USACO16DEC] Cow Checklist G
https://www.luogu.com.cn/problem/P2848
题解：代码中加入了注释
AC代码
代码语言：javascript复制// 题目: P2848 [USACO16DEC] Cow Checklist G
// 链接: https://www.luogu.com.cn/problem/P2848
// 难度: 提高 /省选−
// 题解:
// - 洛谷: https://www.luogu.com.cn/problem/solution/P2848
// - USACO: https://usaco.guide/problems/usaco-670-cow-checklist/solution
#include <bits/stdc .h>
using namespace std;
const int MAX_NUM = 1e3 5;
long long dp[MAX_NUM][MAX_NUM][2];
int n, m;
struct pos {
int x, y;
} h[MAX_NUM], g[MAX_NUM];
long long dis(pos a, pos b) { // 欧几里得距离公式
return (b.x - a.x) * (b.x - a.x) (b.y - a.y) * (b.y - a.y);
}
void best_coder() {
cin >> n >> m;
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i) {
cin >> h[i].x >> h[i].y;
}
for (int i = 1; i <= m; i) {
cin >> g[i].x >> g[i].y;
}
dp[1][0][0] = 0;
for (int i = 1; i <= n; i) { // 选择前i个Holsteins奶牛和前j个Guernseys最后一个选的是Holsteins/Guernseys奶牛耗费的最小能量
for (int j = 0; j <= m; j) {
dp[i][j][0] = min(dp[i][j][0], // 最后停留在Holsteins奶牛，那么转移之前一定是只选择了i - 1个Holsteins奶牛和j个Guernseys
min(dp[i - 1][j][0] dis(h[i - 1], h[i]),
dp[i - 1][j][1] dis(g[j], h[i])));
if (j) { // j要从0开始，因为可以一口气只选Holsteins奶牛，但是j为0时j - 1会爆所以特判一下，不加30分没了……
dp[i][j][1] = min(dp[i][j][1],
min(dp[i][j - 1][0] dis(h[i], g[j]),
dp[i][j - 1][1] dis(g[j - 1], g[j])));
}
}
}
cout << dp[n][m][0]; // 题目要求最后是Holsteins奶牛
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
代码规范
原本34~40行代码是这样
代码语言：javascript复制 dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][0] dis(h[i - 1], h[i]), dp[i - 1][j][1] dis(g[j], h[i])));
if (j) {
dp[i][j][1] = min(dp[i][j][1], min(dp[i][j - 1][0] dis(h[i], g[j]), dp[i][j - 1][1] dis(g[j - 1], g[j])));
}
老码农语重心长的跟我唠叨：要注意代码规范：
- 代码太长，影响阅读；
- 适当换行，上下行代码对比，容易发现代码问题。
对的“唠叨”还是要听的。所以代码就改成这样了。的确层次关系更清晰。
代码语言：javascript复制 dp[i][j][0] = min(dp[i][j][0], // 最后停留在Holsteins奶牛，那么转移之前一定是只选择了i - 1个Holsteins奶牛和j个Guernseys
min(dp[i - 1][j][0] dis(h[i - 1], h[i]),
dp[i - 1][j][1] dis(g[j], h[i])));
if (j) { // j要从0开始，因为可以一口气只选Holsteins奶牛，但是j为0时j - 1会爆所以特判一下，不加30分没了……
dp[i][j][1] = min(dp[i][j][1],
min(dp[i][j - 1][0] dis(h[i], g[j]),
dp[i][j - 1][1] dis(g[j - 1], g[j])));
}
今天就分享到这里，继续刷题。
