You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

3.3 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 1018. 最低通行费

一、题目描述

一个商人穿过一个 N×N 的正方形的网格,去参加一个非常重要的商务活动。

他要从网格的 左上角 进,右下角 出。

每穿越中间 1 个小方格,都要花费 1 个单位时间。

商人必须在 (2N1) 个单位时间穿越出去。

而在经过中间的每个小方格时,都需要 缴纳 一定的费用。

这个商人期望在规定时间内用 最少费用 穿越出去。

请问至少需要多少费用?

注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。

输入格式 第一行是一个整数,表示正方形的宽度 N

后面 N 行,每行 N 个不大于 100 的正整数,为网格上每个小方格的费用。

输出格式 输出一个整数,表示至少需要的费用。

数据范围

1N100

输入样例

5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33

输出样例

109

样例解释 样例中,最小值为 109=1+2+5+7+9+12+19+21+33

二、题目分析

摘花生 与这道题特别相似,摘花生是从左上走到右下角,只能是向下或者向右走,不能回头走,问我们摘到的 最大值 是多少?

这道题要求在2*n-1的时间内,从左上角走到右下角,最小花费 是多少?

理解一下这个2*n-1,如果我们不走回头路的话,那么需要走2*n-1步,所以消耗的时间为2*n-1单位时间。

换句话说,就是只能 向右或向下走不能向左或向上,否则不能在2*n-1步中走到右下角。

分析完2*n-1,就明白这道题其实就是摘花生那道题,只不过不是求最大值,而是求最小值即可。

三、二维数组

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n;
int w[N][N], f[N][N];

int main() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> w[i][j];

    //初始化为最大值
    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1)
                f[i][j] = w[i][j]; //特事特办,不用追求完美的一体化表现,合理特判,逻辑简单
            else
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }

    printf("%d\n", f[n][n]);
    return 0;
}

四、一维数组

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int w[N][N], f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> w[i][j];

    //初始化为最大值
    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1)
                f[j] = w[i][j];
            else
                f[j] = min(f[j], f[j - 1]) + w[i][j];
        }
    printf("%d\n", f[n]);
    return 0;
}