2708 - 矩阵取数游戏
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下： 1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾； 3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
题目输入
输入文件game.in包括n+1行； 第一行为两个用空格隔开的整数n和m。 第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开
题目输出
输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大的分。
输入/输出样例
题目输入
2 3 1 2 3 3 4 2
题目输出
82
提示
【输入输出样例1解释】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6 第2次：两行均取行首元素，本次得分为2*22+3*22=20第3次：得分为3*23+4*23=56。总得分为6+20+56=82
C++解答
#include<bits/stdc++.h> #define lll __int128 void print(lll x) { if (x==0) return; if (x) print(x/10); putchar(x%10+'0'); } int n,m; lll ans=0; int a[100]={0}; lll f[100][100]; lll p[100]={1}; lll dp() { memset(f,0,sizeof(f)); for(int i=1;i<=m;i++) { for(int j=m;j>=i;j--) { f[i][j]=std::max( f[i-1][j]+ p[m-j+i-1]*a[i-1] , f[i][j+1]+ p[m-j+i-1]*a[j+1] ); } } lll maxn=-1; for(int i=1;i<=m;i++) maxn=std::max(maxn,f[i][i]+a[i]*p[m]); return maxn; } int main() { for(int i=1;i<=90;i++) p[i]=p[i-1]<<1; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",a+j); ans+=dp(); } if(ans==0) puts("0"); else print(ans); return 0; }
提示
【输入输出样例1解释】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6 第2次：两行均取行首元素，本次得分为2*22+3*22=20
第3次：得分为3*23+4*23=56。总得分为6+20+56=82