题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n \times mn×m 的矩阵，矩阵中的每个元素 a_{i,j}ai,j​ 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 nn 个。经过 mm 次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 \times 2^i×2i，其中 ii 表示第 ii 次取数（从 11 开始编号）；
4. 游戏结束总得分为 mm 次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式

输入文件包括 n+1n+1 行：

第一行为两个用空格隔开的整数 nn 和 mm。

第 2\sim n+12∼n+1 行为 n \times mn×m 矩阵，其中每行有 mm 个用单个空格隔开的非负整数。

输出格式

输出文件仅包含 11 行，为一个整数，即输入矩阵取数后的最大得分。

输入数据 1

2 3
1 2 3
3 4 2

Copy

输出数据 1

82

Copy

数据范围与约定

对于 60\%60% 的数据，满足 1\le n,m\le 301≤n,m≤30，答案不超过 10^{16}1016。 对于 100\%100% 的数据，满足 1\le n,m\le 801≤n,m≤80，0\le a_{i,j}\le10000≤ai,j​≤1000。

NOIP 2007 提高组 第三题

变更记录

因本题原题与P0769 字符串的展开重复

本题更换为# [NOIP2007提高组] 矩阵取数游戏 

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct dzs{int ws,li[20];
};
int a[81][81],n,m;
dzs f[2][81][81][81],er[81],an,ans,pss1,pss2;
dzs gjc(int p1,dzs p2){   //高精乘单精for(int i=1;i<=p2.ws;i++)p2.li[i]*=p1;for(int i=1;i<=p2.ws+5;i++){if(i>p2.ws&&p2.li[i]!=0)p2.ws=i;if(p2.li[i]>9999)p2.li[i+1]+=p2.li[i]/10000,p2.li[i]%=10000;}return p2;
}
dzs gjj(dzs p1,dzs p2){   //高精加dzs p3;memset(p3.li,0,sizeof(p3.li));p3.ws=1;for(int i=1;i<=max(p1.ws,p2.ws);i++)p3.li[i]=p2.li[i]+p1.li[i];for(int i=1;i<=p2.ws+5;i++){if(i>p3.ws&&p3.li[i]!=0)p3.ws=i;if(p3.li[i]>9999)p3.li[i+1]+=p3.li[i]/10000,p3.li[i]%=10000;}return p3;
}
dzs maxd(dzs p1,dzs p2){  //取大数if(p1.ws>p2.ws)return p1;if(p2.ws>p1.ws)return p2;for(int i=p1.ws;i>=1;i--){if(p1.li[i]>p2.li[i])return p1;if(p1.li[i]<p2.li[i])return p2;}return p1;
}
int print(dzs p1){for(int i=p1.ws;i>=1;i--){if(i==p1.ws){cout<<p1.li[i];continue;}if(p1.li[i]<10)cout<<"000";else if(p1.li[i]<100)cout<<"00";else if(p1.li[i]<1000)cout<<"0";cout<<p1.li[i];}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];er[1].li[1]=2;er[1].ws=1;for(int i=2;i<=m;i++){er[i]=gjc(2,er[i-1]);}//计算2^i(gao jing)for(int k=1;k<=n;k++)//第k行for(int i=1;i<=m;i++){//第i次取数for(int j=1;j<=i;j++){f[0][k][i][j]=gjj(maxd(f[0][k][i-1][j-1],f[1][k][i-1][m-(i-j)+1]),gjc(a[k][j],er[i]));}for(int j=m-i+1;j<=m;j++){f[1][k][i][j]=gjj(maxd(f[1][k][i-1][j+1],f[0][k][i-1][i-(m-j+1)]),gjc(a[k][j],er[i]));}}memset(ans.li,0,sizeof(ans.li));ans.ws=1;for(int k=1;k<=n;k++){an.ws=1;memset(an.li,0,sizeof(an.li));for(int i=1;i<=m;i++){an=maxd(an,f[0][k][m][i]);an=maxd(an,f[1][k][m][i]);}ans=gjj(ans,an);}print(ans);cout<<endl;return 0;
}