Problem 3723 --矩阵取数游戏

3723: 矩阵取数游戏

"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素
aij均为非负整数。游戏规则如下:
1、每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素;
2、每次取走的各个元素只能是该元素所在行的行首或行尾;
3、每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的
元素值*2i ,其中i表示第i次取数(从 1 开始编号);
4、游戏结束总得分为 m 次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
输入包括 n+1 行:
第 1 行为两个用空格隔开的整数 n 和 m。

第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。


60%的数据满足:1<=n, m<=30, 答案不超过 1016
100%的数据满足:1<=n, m<=80, 0<=aij<=1000

仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。
2 3 
1 2 3 
3 4 2
82
【输入输出样例  解释】
第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21 +2*21 =6
第 2 次:两行均取行首元素,本次得分为 2*22 +3*22 =20
第 3 次:得分为 3*23 +4*23 =56。总得分为 6+20+56=82

推荐代码 查看3723 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛