洛谷 P1005 矩阵取数游戏(python版)

题目描述

帅帅与同学常玩一种矩阵取数的娱乐活动：针对一个给定的n*m矩阵，其中所有元素aij均为非负整数。游戏的具体规则如下：

1. 每次取数时，必须从每一行中取出一个元素，总计n个，经过m次操作后将矩阵中的所有元素取完；

2. 每次所取的元素仅限于该行的最左侧或最右侧；

3. 每次取数都会产生相应的得分，该得分是各行得分之和。而每行的得分计算方式为：被取出元素的数值乘以2的i次方，其中i代表此次取数的操作次数（从1开始计数）；

4. 游戏最终总得分为所有m次操作所得分数的累加。

帅帅希望你能编写一个程序，针对任意输入的矩阵，计算出在该游戏规则下所能获得的最大得分。

输入输出格式设计

输入格式：

输入文件game.in共包含n+1行内容：

第一行中包含两个由空格分隔的整数n和m。

接下来的n行构成一个n乘m的矩阵，每行由m个以单个空格分隔的非负整数组成。

数据范围说明：

对于60%的数据，满足条件：1<=n, m<=30，且最终结果不超过10^16

对于全部数据，满足条件：1<=n, m<=80，且每个元素aij的取值范围为0到1000

输出格式：

输出文件game.out仅需输出一行内容，该行包含一个整数，表示从输入矩阵中取数后所能获得的最大得分。

说明

NOIP 2007 提高组第三题

进行一番粗略分析。