#T1574. 矩阵取数游戏
矩阵取数游戏
题目描述
帅帅经常和同学玩一个矩阵取数游戏:对于给定的 𝑛×𝑚 的矩阵,矩阵中每个元素𝑎𝑖𝑗 均为非负整数。游戏规则如下:
1、每次取数时必须从每行各取走一个元素,共 𝑛 个,𝑚 次取完所有元素。
2、每次取走的各个元素只能是该元素所在行行首或行尾。
3、每次取数都有一个的分值,为每行取数得分之和,每行取数得分==被取走元素值2𝑖 ,其中𝑖 表示第 𝑖 次取数,从 1 开始计数。
4、游戏结束时,总得分为 𝑚 次取数得分之和。
帅帅想让你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
输入
输入包括 𝑛+1 行。 第一行两个空格隔开的正整数 𝑛,𝑚 接下来 𝑛 行每行 𝑚 个用空格隔开的整数。
输出
输出为一个整数,为所输入矩阵取数后的最大得分。
样例
2 3
1 2 3
3 4 2
82
提示
数据范围与提示:对于 100% 的数据,。