最低通行费
题目 最低通行费
思路分析
通过案例模拟可以发现其实很像图论里的dfs问题 （这里好像可以用最短路 发现每一步好像都是贪心选的最小 或许拿这道题来分析迪杰斯特拉和spfa好像更合适）
但这题用暴搜的话会超时
也不难发现和摘花生差不多 不过是多了两个东西——可以从上下左右走
这里有个证明 说只能往右和往下走最优 然后就是完全一样的摘花生题
起点是左上角的方块 (1,1)，而终点是右下角的方块 (n,n) 而每次移动，只能走到四相邻的格子中
四相邻：
我们常在一个矩阵中说四相邻，说的就是以当前格子为中心，上、下、左、右四个方向相邻的格子
也就是对于(x,y)来说的(x−1,y),(x+1,y),(x,y−1),(x,y+1)的四个格子
因此，我们在矩阵中找任意两个点之间的距离，用到的不是欧式距离，而是曼哈顿距离
这题用的就是曼哈顿距离
我们可以模拟一下(1,1)到(2,2)的曼哈顿距离，答案是2 而我们从(1,1)出发走到(2,2)的最短距离路线分别是，路线长度也是2 而对于起点的(1,1)到终点(n,n)，它们之间的曼哈顿距离是2n−2 而本题又要求我们在 2n−1的时间内，从起点走到终点
因此，得出结论，我们的走的路线不是完全随机的，而是遵循最短路的原则走的
也就是说，每次移动，至少要使曼哈顿距离缩短 1 于是，规定了我们每次在不越过边界的情况下只能向右或向下移动
emm
反正照着摘花生的写法来就行了 此时属性变成了min
状态表示：f[i][j]：所有从起点出发 走到ij坐标处的所有方案中总价值最小的
状态转移：f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];
因为是最小值 之前在背包dp中也分析过了
初始化的时候要除第一个位置外都置为inf
一个拓展知识点：
min怎么传多个参数
在C++11之前，min函数只接受两个参数，但是C++11引入了可变参数模板的概念，这使得min函数能够接受任意数量的参数。这种参数传递方式称为初始化列表（initializer_list）。
在这个特定的情况中，min函数接受了一个由大括号包围的初始化列表，其中包含了三个值：f[i][j]、f[i][j - 1] + w[i][j]、f[i - 1][j] + w[i][j]。这些值将被逐个比较，然后返回最小的那个值。
所以，min函数在这里的语法是这样的：
min({value1, value2, value3, ...});
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N][N];
int f[N][N];
int 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);
f[1][1]=w[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
/*
这里需要特判（1，1）
如果不特判（1，1）分别可以从（1，0）or（0，1）过来
这两点的值为正无穷，且f[i][j]的属性是min
f[1][1]是从这两个无穷大的数更新过来的
摘花生不用特判的原因是求得max
（1，1）无论从（1，0）or（0，1）来都是0
所以不影响结果不需要特判
*/
if (i == 1 && j == 1)
f[i][j] = w[i][j];
else
f[i][j] = min(f[i][j - 1], f[i - 1][j]) + w[i][j];
//或者直接用这个 合并 省去特判
//f[i][j]=min({f[i][j], f[i][j - 1] + w[i][j], f[i - 1][j] + w[i][j]});
}
}
cout<<f[n][n];
return 0;
}
💬 评论