杭州公司注销网站备案,建局域网网站,首页制作,东莞网站建设服务最低通行费用
原题链接
AcWing 1018. 最低同行费用
题目描述
一个商人穿过一个 NN的正方形的网格#xff0c;去参加一个非常重要的商务活动。 他要从网格的左上角进#xff0c;右下角出。每穿越中间 1个小方格#xff0c;都要花费 1个单位时间。商人必须在 (2N−1)个单位…最低通行费用
原题链接
AcWing 1018. 最低同行费用
题目描述
一个商人穿过一个 N×N的正方形的网格去参加一个非常重要的商务活动。 他要从网格的左上角进右下角出。每穿越中间 1个小方格都要花费 1个单位时间。商人必须在 (2N−1)个单位时间穿越出去。 而在经过中间的每个小方格时都需要缴纳一定的费用。 这个商人期望在规定时间内用最少费用穿越出去。 请问至少需要多少费用 注意不能对角穿越各个小方格即只能向上下左右四个方向移动且不能离开网格。
输入格式 第一行是一个整数表示正方形的宽度 N。后面 N行每行 N个不大于 100的正整数为网格上每个小方格的费用。 输出格式 输出一个整数表示至少需要的费用。
数据范围 1≤N≤100
输入样例
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样例解释 样例中最小值为 1091257912192133。
题目分析
“商人必须在 (2N−1)个单位时间穿越出去” 意味着不能走回头路 因此该题转化为 “ 摘花生 ”。
不同点在于该题 “最低通行费” 所求为最小值min而 “摘花生” 所求为最大值max。
全局变量的初值默认为0最小值min在求解过程中可能涉及到初始化问题因为0可以是最小值而边界情况又是不合理的需要我们多加处理。
数据的初始化处理
第一列 i1 路径不可能来自第一列的左侧f[i][0] 初始化为INF。 第一行1j 路径不可能来自第一行的上侧f[0][j] 初始化为INF。
同时在状态计算的过程当中路径一定过起点11因此f[1][1]的状态值不由f[0][1]或者f[1][0]得到而是直接赋值为 w[1][1]。
完整代码
#include iostream
#include algorithm
using namespace std;
const int N110;
const int INF2e9;
int n;
int w[N][N]; //费用
int f[N][N]; //状态表示
int main(){scanf(%d,n);for(int i1;in;i){for(int j1;jn;j){scanf(%d,w[i][j]);}}//初始化处理for(int i1;in;i){f[i][0]INF; //第一列的左侧f[0][i]INF; //第一行的上侧}//状态计算for(int i1;in;i){for(int j1;jn;j){if(i1j1) f[1][1]w[1][1]; //如果是起始点(1,1)则直接赋值w[1][1]else f[i][j]min(f[i-1][j],f[i][j-1])w[i][j]; //否则通过状态计算}}printf(%d,f[n][n]); //右下角终点(n,n)的f状态值即为最终答案return 0;
}
