首页 > 试题广场 >

矩阵取数游戏

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

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

输入

[[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

输入

[[4,5,0,5]]

输出

122
示例3

输入

[[96,56,54,46,86,12,23,88,80,43],[16,95,18,29,30,53,88,83,64,67]]

输出

316994
算法知识视频讲解
添加回答
Java
牛客345463252号头像 牛客345463252号
用数太大了，所以要用bigInteger 
import java.util.*; 
import java.math.BigInteger;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    int mod=(int)1e9+7;
    BigInteger bigIntMod=BigInteger.valueOf(mod);
    int process(List<Integer> list,BigInteger[] pow){
        int n=list.size();
        BigInteger[][] dp=new BigInteger[n][n];
        for(int i=0;i<n;i++){
            dp[i][i]=BigInteger.valueOf(list.get(i)).multiply(pow[n]);
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                int k=n-j+i;
                BigInteger l=dp[i][j-1].add(pow[k].multiply(BigInteger.valueOf(list.get(j))));
                BigInteger r=dp[i+1][j].add(pow[k].multiply(BigInteger.valueOf(list.get(i))));
                if(l.compareTo(r)<0){
                    dp[i][j]=r;
                }else{
                    dp[i][j]=l;
                }
            }
        }
        return dp[0][n-1].mod(bigIntMod).intValue();
    }
    public int matrixScore (ArrayList<ArrayList<Integer>> matrix) {
        // write code here
        int res=0;
        int n = matrix.size();
        n=matrix.get(0).size();
        BigInteger[] pow=new BigInteger[n+1];
        pow[0]=new BigInteger("1");
        BigInteger base=BigInteger.valueOf(2);
        for(int i=1;i<=n;i++){
            pow[i]=pow[i-1].multiply(base);
        }
        for(int i=0;i<matrix.size();i++){
            res=(res+process(matrix.get(i),pow))%mod;
        }
        return res;
    }
}
发表于 2023-03-19 15:37:52 回复(0)
JavaScript Node
几号发货头像 几号发货

思路:

  1. 各行的数据选择毫不相关,可以认为是rows次选择
  2. dp[i][j]指当前行剩余[i,j]这些数据可以选择时,可能获取的最大值
  3. 转移方程显而易见就是dp[i][j] = Math.max(dp[i + 1][j] + matrix[row][i] * (1 << (m - len)), dp[i][j - 1] + matrix[row][j] * (1 << (m - len))) 
// 由于row行数据之间的计算相互独立,可以看成row次单行的计算
function matrixScore(matrix) {
  let n = matrix.length
  let m = matrix[0].length
  // dp[i][j] 表示对于剩余[i,j]数据,可能获取的最大值
  let dp = new Array(m + 1).fill(0).map(i => new Array(m + 1).fill(0))
  const MOD = 1e9 + 7
  let res = 0
  for (let row = 0; row < n; row++) {
    for (let j = 0; j < m; j++) {
      // 仅剩[j,j]这一个数据,获取最大值只能是如下:(1 << n) 表示 2**n
      dp[j][j] = ((1 << m) * matrix[row][j]);
    }
    for (let len = 1; len < m; len++) {
      for (let i = 0; i < m - len; i++) {
        let j = i + len
        dp[i][j] = Math.max(dp[i + 1][j] + matrix[row][i] * (1 << (m - len)), dp[i][j - 1] + matrix[row][j] * (1 << (m - len)))
      }
    }
    res = (res + (dp[0][m - 1] % MOD)) % MOD
  }
  return res
}
发表于 2022-11-20 21:04:42 回复(0)
提交观点

问题信息

动态规划
难度：
2条回答 1371浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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