yxy

用户名：dotcpp0787179

访问量：497

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

多源bfs-[信息学奥赛一本通T1449-魔板]-洛谷绿
浏览：31

双端队列deque+bfs--[信息学奥赛一本通T1452-Keyboarding] 原题变形：ACM-ICPC-WORLD-FINALS-2015
浏览：32

[食物链] 并查集 - NOI2001 提高组
浏览：22

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

A+B for Input-Output Practice （C++代码）

dp--数字三角形模型//闫氏dp法[最低通行费]

　　作者: yxy　　　　发表时间：2024-09-16 02:41:38 浏览：25　|　评论：0　

原题链接：最低通行费

#数字三角形模型 进阶版
## 闫氏dp法
数字三角形模型dp基础题 链接 ：[数字三角形模型题](https://www.dotcpp.com/oj/problem2127.html "数字三角形模型题")

![](/image_editor_upload/20240916/20240916023355_13524.png)

###### 此题为数字三角形模板 不懂的请看 链接 ：[数字三角形模型题](https://www.dotcpp.com/oj/problem2127.html "数字三角形模型题")

###### 从两个方向思考 商人可以从上面下来 也可以从左边到右边
###### 很明显了 我们的状态转移有 f[i,j] = min(f[i,j] , f[i-1,j] + a[i,j]) 以及f[i,j] = min(f[i,j] , f[i-1,j] + a[i,j])  // ts：a为地图数组

###### 但是 需要注意的是 题目所说 必须从左上角出发 也就是不存在 i==1的时候从左边过来以及j==1的时候从上面过来

下面开始AC：
###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long //个人习惯 有备无患
using namespace std;
const int N = 1010 , INF = 1e9; 
int n , a[N][N];
int f[N][N];

signed 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] = INF;  //将f理论最大化 方便取min
                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;
}
```

###### 题解不宜 求赞

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

字符串的输入输出处理（C语言代码）

A+B for Input-Output Practice （C++代码）

dp--数字三角形模型//闫氏dp法[最低通行费]

评论区

精彩推荐

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

字符串问题（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

字符串的输入输出处理 （C语言代码）

A+B for Input-Output Practice （C++代码）

dp--数字三角形模型//闫氏dp法[最低通行费]

评论区

精彩推荐

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

字符串问题 （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

程序员的表白（C语言代码）

字符串问题（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

校门外的树（C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）