题目描述
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用?
样例
输入样例:
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
算法
(暴力枚举) $O(n^2)$
该题和摘花生不同的点就是取最小值。
而,如果要取到最小值,那么矩阵需要初始化,从而迫使第一行和第一列只能从特定的方向过来。
(最大值不需要,因为矩阵初始化就是0,而有数的地方肯定比0大)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int g[N][N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> g[i][j];
// 初始化第一行和第一列
for (int i = 0; i <= n; i ++ ) f[i][0] = f[0][i] = 1e9;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == 1 && j == 1) f[i][j] = g[i][j];
else
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j];
// 特判:最开始就是自己
cout << f[n][n] << endl;
return 0;
}
另外,除了初始化第一行和第一列之外,还可以写成特判的形式
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int a[N][N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> a[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
if (i == 1 && j == 1) f[i][j] = a[i][j];
else
{
f[i][j] = 1e9; // 需要初始化,不然它的值就是0
if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + a[i][j]);
if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + a[i][j]);
}
}
cout << f[n][n] << endl;
return 0;
}