信息学奥赛一本通 1287:最低通行费(evd)
发布日期:2022-01-30 02:41:35 浏览次数:13 分类:技术文章

本文共 885 字,大约阅读时间需要 2 分钟。

【题目描述】

一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动。他要从网格的左上角进,右下角出。每穿越中间1个小方格,都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时,都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用?

注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。

【输入】

第一行是一个整数,表示正方形的宽度N (1≤N<100);

后面N行,每行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
【心得】说的好像上下左右都能走,可时间却限制,为2*N-1,所以只能向下或者向右走,这不就是1284(摘花生)了吗?只是现在要的是最小值!但是一定要注意边界!
【AC代码】

#include
#include
#include
using namespace std;const int N=105;const int IMAX=0x7fffffff;int n,a[N][N],f[N][N];int main(){
cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int i=0;i<=n;i++) f[0][i]=f[i][0]=IMAX; for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i==1&&j==1) f[1][1]=a[1][1]; else f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j]; } } cout<
<

转载地址:https://blog.csdn.net/everwide1982/article/details/109750269 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:信息学奥赛一本通 1286:怪盗基德的滑翔翼(evd)
下一篇:信息学奥赛一本通 1289:拦截导弹(evd)

发表评论

最新留言

很好
[***.229.124.182]2024年03月04日 10时18分51秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

中考大数据大连79_中考大数据 | 大连部分初中2019年中考指标生录取最低分及人数统计!... 2019-04-21
vue 地理位置定位_HTML5地理位置 2019-04-21
pac代理模式什么意思_托管仓库租赁电商仓储运营模式托管什么意思 2019-04-21
validated 验证数组_在 Laravel 中处理请求验证的智能方法 2019-04-21
洞泾智能机器人产业基地_G60科创走廊洞泾人工智能产业基地(核心区块)暨洞泾镇招商人员培训班顺利开班... 2019-04-21
java 拼接路径优雅方式_Java安全编码实践总结 2019-04-21
realme x2 深度测试打不开_搭载65W超级闪充,realme真我X7手机充电评测 2019-04-21
整数取反编程_【每日编程185期】数字的补数 2019-04-21
能用别的软件吗_手机软件能用蓝牙传送吗 2019-04-21
为什么图片要2的倍数_为什么宝宝喜欢流“口水”?这种2种原因父母要知道,建议收藏... 2019-04-21
下载了XAMPP怎样打开MYSQL_xampp mysql安装启动 2019-04-21
pdo转mysql_mysql转mysqli或pdo 2019-04-21
mysql如果没有表就创建_mysql – 改变表是否存在或创建如果没有 2019-04-21
ireport连接mysql_ireport 4.5教程之数据源介绍 2019-04-21
mysql多维模型_数据仓库数据库设计方法---关系模型和多维模型比较分析 2019-04-21
局域网聊天程序 java MySQL_java 基于TCP/IP协议的局域网聊天小程序 2019-04-21
r glm 中的p值_假设检验中的P值 2019-04-21
mysql中sql语句结构_MySQL中使用sql语句获得表结构 2019-04-21
如何增加mysql主键约束_mysql修改表时怎么添加主键约束? 2019-04-21
java选择路径窗口_Java实现选择电脑路径的方法 2019-04-21