网络营销推广咨询收费标准,北京网站关键词优化推荐,qq空间怎么发布wordpress,陕西泰烜建设集团网站点我写题
题目描述
帅帅经常跟同学玩一个矩阵取数游戏#xff1a;对于一个给定的n*m的矩阵#xff0c;矩阵中的每个元素aij均为非负整数。游戏规则如下#xff1a; 1.每次取数时须从每行各取走一个元素#xff0c;共n个。m次后取完矩阵所有元素#xff1b; 2.每次取走的…点我写题
题目描述
帅帅经常跟同学玩一个矩阵取数游戏对于一个给定的n*m的矩阵矩阵中的每个元素aij均为非负整数。游戏规则如下 1.每次取数时须从每行各取走一个元素共n个。m次后取完矩阵所有元素 2.每次取走的各个元素只能是该元素所在行的行首或行尾 3.每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值 * 2i其中i表示第i次取数从1开始编号 4.游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。
示例1
输入
复制
2 3
1 2
3 4 2
输出
复制
82
思路容易观察到每列可以单独考虑即局部最优解能构成全局最优解设dp[i][t][k]表示n*m的矩阵中第i行元素到第t轮选元素前面选了k个的最大值。
转移考虑当前轮是选前面的还是选后面的选前面的就是dp[i][t][k]dp[i][t-1][k-1]a[k]*(2^t),选后面的dp[i][t][k]dp[i][t-1][k]a[m-(t-k)1]*(2^t)即前面选k个后面就该选了t-k个了。
ps:这里还硬缝合了个高精度但是java用BigInteger就能过java果然是世界上最好的语言bushi~。
纠错:牛客空间比较大三维dp能过但是洛谷只能俩维把没用的那维去掉就好了然后加个初始化。
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner snew Scanner(System.in);int ns.nextInt(),ms.nextInt();int a[][]new int [n10][m10];BigInteger mul[]new BigInteger [m10];mul[0]BigInteger.valueOf(1);for(int i1;im;i) mul[i]mul[i-1].multiply(BigInteger.valueOf(2));for(int i1;in;i) {for(int j1;jm;j) {a[i][j]s.nextInt();}}BigInteger ansBigInteger.valueOf(0);for(int i1;in;i) {BigInteger resBigInteger.valueOf(0);BigInteger dp[][]new BigInteger [m10][m10];for(int j0;jm;j) {for(int k0;km;k) {dp[j][k]new BigInteger(0);}}for(int t1;tm;t) {for(int j0;jt;j) {dp[t][j]dp[t-1][j].add(BigInteger.valueOf(a[i][m-(t-j)1]).multiply(mul[t]));if(j0) {BigInteger xdp[t-1][j-1].add(mul[t].multiply(BigInteger.valueOf(a[i][j])));if(dp[t][j].compareTo(x)0) dp[t][j]x;}if(res.compareTo(dp[t][j])0) resdp[t][j];}}ansans.add(res);}System.out.print(ans\n);}}
