网格DP：USACO Cow Checklist G，注意代码规范

小码匠

发布于 2024-02-21 13:19:35

720

发布于 2024-02-21 13:19:35

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

昨天下午继续刷题，老码农管用的伎俩，给我找了4道题，自己从中选题做。

作为一个爱躺平的咸鱼，一眼相中了这道题：P2848 [USACO16DEC] Cow Checklist G

我瞄了一眼评论区，看有人要求：建议评黄, 现在是：提高+/省选，估计这题就不难，就它了，是我喜欢的菜。

题目：P2848 [USACO16DEC] Cow Checklist G

https://www.luogu.com.cn/problem/P2848

题解：代码中加入了注释

AC代码

// 题目: 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行代码是这样

            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])));
            }

老码农语重心长的跟我唠叨：要注意代码规范：

代码太长，影响阅读；
适当换行，上下行代码对比，容易发现代码问题。

对的“唠叨”还是要听的。所以代码就改成这样了。的确层次关系更清晰。

            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])));
            }

今天就分享到这里，继续刷题。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除