信息学奥赛一本通 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年03月04日 10时18分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
vue 地理位置定位_HTML5地理位置
2019-04-21
pac代理模式什么意思_托管仓库租赁电商仓储运营模式托管什么意思
2019-04-21
validated 验证数组_在 Laravel 中处理请求验证的智能方法
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