首页 > 试题广场 >

[NOIP2007]矩阵取数游戏

[编程题][NOIP2007]矩阵取数游戏
  • 热度指数：96 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。


输入描述:
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。


输出描述:
输出一个整数，即输入矩阵取数后的最大得分。
示例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
示例2

输入

1 4
4 5 0 5

输出

122
示例3

输入

2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

输出

316994

备注:
60%的数据满足：1 ≤ n, m ≤ 30, 答案不超过1016
100%的数据满足：1 ≤ n, m ≤ 80, 0 ≤ aij ≤ 1000
算法知识视频讲解
开通博客
头像 江三
发表于 2020-07-11 20:31:11
一.题意 n*m 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * 2 ^ i ，i 为第 i 次取数且每次取走的各个元素只能是该元素所在行的行首或行尾，取 m 次，求取数的最大得分和。 二.题解 因为每次只能取行首或者行尾，所以每行取得顺序都是独立的。由此可以从 求最大的得分和 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2020-07-11 11:41:37
感觉这种形式得动态规划也有很多类型，反正就是从两边取数，按照一定得规则把这个数做一个计算。题解：看这个题，他问的是一个矩阵如何取数，我们可以发现，对于每一行如何取数，题目中只是说从两边取，并没有说明行与行之间的要求，那么这个问题就可以化简一下了，我们对每行进行动态规划，分别求出每行如何取数的最大值然 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 19-hanhan
发表于 2020-07-16 01:37:21
题目 题目描述： 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2.每次取走的各个元素只能是该元素所在行的行首或行尾； 3.每次取数都有一个得分值，为每行 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 WarYan
发表于 2020-07-15 15:05:30
链接：https://ac.nowcoder.com/acm/problem/16645来源：牛客网 题目描述 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的nm的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2. 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 ExcaIibur
发表于 2020-08-24 22:16:45
题目链接 题意：有一n行m列的矩阵，每次从这n行中取出行首或行尾的数，一个数的权值为 val*2^i，该次得分为这n行取值总和，共取m次，求最大权值和。 题解： 虽然数据较大，但用 int128 完全可以存下。由于取行首或行尾操作容易用转移方程描述，考虑动态规划。设 pw[i]为对应2的幂，a 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kur1su
发表于 2020-07-10 14:59:37
Description 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-07-14 22:04:06
题意：给出一个n*m的矩阵，每一次取数从每一行中取一个数，每行取数的得分为每行所取数a[i][j] * ,k表示第几次取，且每次取数只能取头或者尾。求取完后的得分最大值？ 思路：我们可以发现每一行的取数只与当前行有关，所以该题相当于求n次数组中取数得分之和。我们可以区间dp解决。每一次不断增加区间 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-10-15 17:06:54
//每次都要在每一层进行取，也就是说层与层之间没有什么关联。x,i和j是区间左右。 //dp[x][i][j] = max(dp[x][i+1][j]+pow(2,n)*a[i][j], dp[x][i][j-1]+pow(2,n)*a[i][j]); //每次都要在每一层进行取，也就是说层 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zzugzx
发表于 2020-07-09 14:24:49
题目链接 题意：题解：AC代码 f = [[0 for i in range(100)] for i in range(100)] n, m = map(int, input().split()) a = [0 for i in range(100)] def dfs(l, r) : len 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunsetcolors
发表于 2020-07-09 15:53:39
NC16645 矩阵取数游戏 题目地址: https://ac.nowcoder.com/acm/problem/16645 基本思路： 首先根据题意我们易发现矩阵的每一行是独立的，因此我们计算出每一行答案再相加就行了。 要计算每一行的答案，我们可以使用区间,设表示这一行范围内的最大取数方案 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

NOIP复赛 动态规划
难度：
1条回答 2056浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号