首页 > 试题广场 >

[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
算法知识视频讲解
添加回答
week_头像 week_
dp没什么好说的。用long dp[][]，可以通过60%的用例，如果要真的考的话，大数运算是肯定要完成的，但是正式考试的时候肯定没人会去实现大数相乘，用biginteger即可AC。 
import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            int m=sc.nextInt();
            int num[][]=new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    num[i][j]=sc.nextInt();
                }
            }
            BigInteger res=new BigInteger("0");
            for(int index=0;index<n;index++){
                //i到j上能取到的最大的分数
                BigInteger dp[][]=new BigInteger[m][m];
                for(int i=0;i<m;i++){
                    dp[i][i]=new BigInteger(2*num[index][i]+"");
                }
                for(int i=m-2;i>=0;i--){
                    for(int j=i+1;j<m;j++){
                        //dp[i][j]=2*Math.max(dp[i][j-1]+num[index][j],dp[i+1][j]+num[index][i]);
                        dp[i][j]=dp[i][j-1].add(new BigInteger(num[index][j]+"")).multiply(new BigInteger("2")).max(
                                dp[i+1][j].add(new BigInteger(num[index][i]+"")).multiply(new BigInteger("2"))
                        );
                    }
                }
                res=res.add(new BigInteger(dp[0][m-1]+""));
            }
            System.out.println(res);
        }
    }
}

发表于 2019-06-12 15:58:54 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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