首页 > 试题广场 >

矩阵取数游戏

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

数据范围： ，矩阵中的值满足 ，由于得分可能会非常大，所以把值对 取模

输入描述:
第一行输入两个正整数 n 和 m ，表示矩阵的长宽。
后续 n 行每行输入 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
算法知识视频讲解
添加回答
towa头像 towa 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <stdio.h>

using namespace std;
using ll = __int128_t;
ll mod = 1e9 + 7;
ll dp[100][100];
ll mat[100];

ll slove(vector<int>& nums, int l, int r, int i) {
    if (i == nums.size()) return 0;
    if (dp[l][r] > 0) return dp[l][r];
    ll left = slove(nums, l + 1, r, i + 1) + nums[l] * mat[i];//容易犯的错误是写nums[l]*(2<<i)这个在计算表达式的时候会认为2是int型然后如果i超过32位就会出错，其结果就是第五个例子不通过
    ll right = slove(nums, l, r - 1, i + 1) + nums[r] * mat[i];
    return dp[l][r] = max(left, right);
}


int main() {
    int n, m;
    //mat保存2^0 - 2^100次方的值
    mat[0] = 2;
    for(int i = 1; i < 100; i++)
        mat[i] = mat[i - 1] * 2;
    while (cin >> n >> m) {
        vector<int>nums(m);
        ll res = 0;
        for (int i = 0; i < n; i++) {
            memset(dp, 0, sizeof(dp));
            for (int j = 0; j < m; j++) {
                scanf("%d", &nums[j]);
            }
            res += slove(nums, 0, m - 1, 0);
        }
        cout << int(res % mod) << endl;
    }
}


发表于 2022-10-18 02:14:49 回复(0)
秋越海头像 秋越海
这道题答案是不是错了啊？得不到预期输出呐。
发表于 2022-05-11 20:16:41 回复(1)
Python3
朱越峰头像 朱越峰
案例5预期输出73892069，实际输出835570668。如果后来的同学也做出来这个结果就反馈一下答案错误吧。
发表于 2022-04-18 13:41:26 回复(0)
Java
wyllyh123456头像 wyllyh123456 
48 49难度从中等改成了较难。。。卡死在案例5，用BigInteger也不行。
😭😭😭
发表于 2022-03-23 14:18:26 回复(0)
神202304021303534头像 神202304021303534
案例5超时，服了呀，照着c++代码改的，根本过不去
发表于 2023-09-03 09:30:38 回复(0)
C++
牛客288355985号头像 牛客288355985号
善用__int128_t 
#include<iostream>
#include<cstring>
using namespace std;

using ll=__int128_t;

ll* a;
ll mat[100][100];
ll cache[100][100];
int n,m;

ll dpline(int l,int r){
  int i=m-r+l;
  if(0<cache[l][r]) return cache[l][r];
  if(i==m) return cache[l][r]=a[r]<<i;
  ll left=dpline(l+1,r)+(a[l]<<i);
  ll right=dpline(l,r-1)+(a[r]<<i);
  return cache[l][r]=max(left,right);
}

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      int num;
      cin>>num;
      mat[i][j]=num;
    }
  }
  ll res=0;
  for(int i=0;i<n;i++){
    ::a=mat[i];
    memset(cache,0,sizeof(cache));
    res=res+dpline(0,m-1);
  }
  cout<<int(res%int(1e9+7))<<endl;
}


发表于 2022-09-02 17:38:01 回复(0)
Python 3
静寂旮旯头像 静寂旮旯
这个题涉及到高精度计算，所以简单一点用python写吧。而且结果是对最终结果取模
发表于 2022-05-26 11:17:16 回复(0)
提交观点

问题信息

动态规划
难度：
7条回答 1492浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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