当前位置:网站首页>7-3 最低通行费
7-3 最低通行费
2022-06-26 12:32:00 【白—】
7-3 最低通行费
一个商人穿过一个 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。
代码:
#include<iostream>
using namespace std;
int main()
{
int n,i,j,a[102][102];
cin>>n;
for (i=0;i<102;i++)
for (j=0;j<102;j++)
a[i][j]=9990;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
cin>>a[i][j];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (i==1&&j==1)
continue;
else
{
if (a[i][j]+a[i][j-1]>a[i][j]+a[i-1][j])
a[i][j]=a[i][j]+a[i-1][j];
if(a[i][j]+a[i][j-1]<=a[i][j]+a[i-1][j])
a[i][j]=a[i][j]+a[i][j-1];
}
}
cout<<a[n][n]<<endl;
return 0;
}
202206260904日
边栏推荐
- Notice on printing and Distributing Measures for supporting strategic emerging industries and future industrial cluster development in Futian District, Shenzhen
- Using the methods in the repository to solve practical problems
- Research on the current situation of China's modified engineering plastics market and demand forecast analysis report 2022-2028
- MOS管基本原理,单片机重要知识点
- Analysis report on dynamic research and investment planning suggestions of China's laser medical market in 2022
- Pre knowledge of hash table -- binary search tree
- Which is safer and better for great wisdom to open an account
- What software is flush? Is online account opening safe?
- The transformation of enterprise customers' digital assets needs to suit the case
- 大智慧哪个开户更安全,更好点
猜你喜欢

4. N queen problem

【概率论】条件概率、贝叶斯公式、相关系数、中心极限定理、参数估计、假设检验

Comparison of latest mobile phone processors in 2020 (with mobile phone CPU ladder diagram)

How to calculate flops and params in deep learning

Introduction to the four major FPGA manufacturers abroad

TSMC Samsung will mass produce 3nm chips in 2022: will the iPhone be the first?

leetcode 715. Range 模块 (hard)

Microservice governance (nocas)

Pre knowledge of hash table -- binary search tree

Loggie encoding and newline character test
随机推荐
菜鸟实战UML——活动图
Oracle lock table query and unlocking method
Lintcode 130 · 堆化
PHP unit conversion
开通证券账户需要注意事项 开户安全吗
【毕业季·进击的技术er】忆毕业一年有感
Jmeter响应时间和tps监听器使用教程
Mqtt disconnect and reconnect
[graduation season · advanced technology Er] I remember the year after graduation
How do consumer goods enterprises formulate membership interests?
大智慧哪个开户更安全,更好点
PHP uses laravel pay component to quickly access wechat jsapi payment (wechat official account payment)
2022 edition of China's medical robot industry investment status investigation and prospect dynamic analysis report
MS17_ 010 utilization summary
Analysis report on dynamic research and investment planning suggestions of China's laser medical market in 2022
Vscode solves the problem of Chinese garbled code
What determines the rent
Cross platform members get through the two channels of brand Ren Du
China's smart toy market outlook and investment strategy consulting forecast report from 2022 to 2027
Build Pikachu shooting range and introduction