动态规划DP 数字三角型模型 最低通行费用(题目详解+C++代码完整实现)
最低通行费用
原题链接
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
样例解释
样例中,最小值为 109=1+2+5+7+9+12+19+21+33。
题目分析
“商人必须在 (2N−1)个单位时间穿越出去” 意味着不能走回头路,
因此,该题转化为 “ 摘花生 ”。
不同点在于,该题 “最低通行费” 所求为最小值(min),而 “摘花生” 所求为最大值(max)。
全局变量的初值默认为0,最小值(min)在求解过程中可能涉及到初始化问题,因为0可以是最小值,而边界情况又是不合理的,需要我们多加处理。
数据的初始化处理
第一列 (i,1):
路径不可能来自第一列的左侧,f[i][0] 初始化为INF。
第一行(1,j):
路径不可能来自第一行的上侧,f[0][j] 初始化为INF。
同时,在状态计算的过程当中,路径一定过起点(1,1),因此,f[1][1]的状态值不由f[0][1]或者f[1][0]得到,而是直接赋值为 w[1][1]。
完整代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
const int INF=2e9;
int n;
int w[N][N]; //费用
int f[N][N]; //状态表示
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&w[i][j]);
}
}
//初始化处理
for(int i=1;i<=n;i++){
f[i][0]=INF; //第一列的左侧
f[0][i]=INF; //第一行的上侧
}
//状态计算
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1) 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;
}
原文地址:https://blog.csdn.net/fcc13461862452/article/details/145383134
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/523953.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/523953.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!