现在有一个 m * n 的整数矩阵,请你编写一个程序计算出一条从左到右穿过矩阵的路径,并使此路径的费用最小。路径从矩阵的左侧的第一列的任意单元格开始,逐步穿过矩阵到达最右侧的一列的任意单元格。每一步是指从某单元格进入它一列的相邻单元格(如下图,可以是横向或斜向)。矩阵的第一行和最后一行实际是相邻的,你可以想象矩阵是包裹在一个横放的圆柱体外面。
路径的花费是指这条路径所穿越的所有单元格中的数字之和。
穿越两个略有不同的 5 * 6 的矩阵的路径如下图所示,这两个矩阵只有最后一行的数字不同。右侧的路径显示了第一行和最后一行相邻的效果。
输入
输入包括一系列矩阵描述。每个矩阵描述的第一行是 m 和 n,即矩阵的行数和列数;之后的 m 行,每行包括 n 个以空格分开的整数,则是当前矩阵的值,注意矩阵的值未必是正数。
矩阵的行数 m 和列数 n 的范围是:1 <= m <= 10、 1 <= n <= 100;所有路径的费用值都可以用 30bit 的整数表示。
输出
针对每一个矩阵,找出费用最小的路径,并将其输出。每个矩阵的输出包括两行,第一行是路径本身,即输出每一步所在的行,第二行则是该路径的费用。
如果对于同一个矩阵有多条不同的费用最小路径,则输出左端行号较小的一条。
来源
UVa: 116
测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
-
56↵
-
341286↵
-
618274↵
-
593995↵
-
841326↵
-
372864↵
-
56↵
-
341286↵
-
618274↵
-
593995↵
-
841326↵
-
372123↵
|
以文本方式显示
|
1秒
|
1024KB
|
0
|
递归的解法:
然而,这并不是一个很好的解法,当矩阵列数超过10时会超过时间限制!
非递归解法:(采用动态规划)
分享到:
相关推荐
矩阵 acm竞赛模版
矩阵快速幂的模板,需要自己根据实际题目更改矩阵大小和数据类型,以免WA和TLE。经过矩阵乘法上的稀疏矩阵优化和int64的乘法取模幂优化,效率应该比较高。视情况使用mult()函数或直接使用乘法。代码中每个函数有注释...
矩阵乘法 ACM,有关矩阵乘法的题目的总结
ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛
动态规划,矩阵连乘,ACM动态规划,矩阵连乘,ACM动态规划,矩阵连乘,ACM动态规划,矩阵连乘,ACM
一些简单的ACM算法:包括蛇行矩阵、找数字对、最小自然数等等。
ACM ACM ACM ACM ACM讲义.ppt
ACM必会-杨氏矩阵题解分析.zip 是一个压缩文件,包含了关于杨氏矩阵问题的详细题解和代码实现。该资源旨在帮助参加ACM竞赛的选手更好地理解杨氏矩阵问题,并提供相应的解决方案和代码示例。 内容概要: 该压缩文件...
ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板AACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM ...
acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 ...
ACM PRO ACM PROACM PRO ACM PROACM PRO ACM PRO
包含近几年多道ACM面试题目,希望有所帮助
acm模板acm模板acm模板acm模板acm模板acm模板acm模板acm模板
ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码
acm经典题库acm经典题库acm经典题库
ACM地址 ACM地址 ACM地址 ACM地址 ACM地址
十个利用矩阵乘法解决的经典题目,适于acm等算法爱好者学习
ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版
ACM练习建议 ACM练习建议 ACM练习建议