题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入输出格式
输入格式：
输入文件game.in包括n+1行：
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
数据范围：
60%的数据满足：1<=n, m<=30，答案不超过10^16
100%的数据满足：1<=n, m<=80，0<=aij<=1000
输出格式：
输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。
这是世界上最丑的高精...然而并不能阻止我AC...
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define M(x) memset(x,0,sizeof(x))
using namespace std;
void ADD(int a[],int b[],int c[]){
],b[]);
;i<=len;i++){
c[i]+=a[i]+b[i];
){
c[i+]+=c[i]/;
c[i]%=;
}
}
]) c[]=len+;
]=len;
}
bool BIGGER(int a[],int b[]){
]==b[]){
];i>=;i--) if(a[i]!=b[i]) return a[i]>b[i];
}]>b[];
}
void C(int a[],int b[],int c[]){
;i<=a[];i++){
;j<=b[];j++){
c[i+j-]+=a[i]*b[j];
}
}
c[]=a[]+b[]+;
;i<=c[];i++){
c[i+]+=c[i]/;
c[i]%=;
}
]]&&c[]>) c[]--;
return;
}
void change(int a,int b[]){
){
b[++b[]]=a%;
a/=;
}b[++b[]]=a;
}
void print(int a[]){
];i>=;i--) printf("%d",a[i]);
}
],v[][],mem[][][],ppow[][];
void dp(int l,int r,int c[]){
if(v[l][r]){
;i<=mem[l][r][];i++) c[i]=mem[l][r][i];
return;
}
v[l][r]=;
memset(mem[l][r],,sizeof(mem[l][r]));
if(l==r){
];M(t);
change(data[l],mem[l][r]);
C(mem[l][r],ppow[m],t);
;i<=t[];i++) mem[l][r][i]=c[i]=t[i];
return;
}
],t3[],t4[],ll[],rr[];
M(t2);dp(l+,r,t2);
M(t3);change(data[l],t3);
M(t4);C(t3,ppow[m-r+l],t4);
M(ll);ADD(t2,t4,ll);
M(t2);dp(l,r-,t2);
M(t3);change(data[r],t3);
M(t4);C(t3,ppow[m-r+l],t4);
M(rr);ADD(t2,t4,rr);
if(BIGGER(ll,rr)){
;i<=ll[];i++) c[i]=mem[l][r][i]=ll[i];
};i<=rr[];i++) c[i]=mem[l][r][i]=rr[i];
return;
}
void calcppow(){
M(ppow);
ppow[][]=;ppow[][]=;
];two[]=;two[]=;
;i<=;i++) C(ppow[i-],two,ppow[i]);
}
int main()
{
calcppow();
],t[],t2[];memset(ans,,sizeof(ans));
scanf("%d%d",&n,&m);
;i<=n;i++){
;j<=m;j++){
scanf("%d",&data[j]);
}
memset(t,,sizeof(t));
memset(v,,sizeof(v));
M(mem);
dp(,m,t);
M(t2);ADD(ans,t,t2);
;i<=t2[];i++) ans[i]=t2[i];
}
print(ans);
;
}