P1005 矩阵取数游戏

输入样例
2 3
1 2 3
3 4 2
输出 样例
82

#include<bits/stdc++.h>
#define in(x) x=read()
#define k m-(R-L)
#define MAXN 81
#define bll __int128
using namespace std;
inline int read()
{
	int X=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') 
	{
		if(ch=='-') w=-1;
		ch=getchar();
	 } 
	while(ch>='0'&&ch<='9')
	 X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
	 return X*w;
}
int n,m;
int num[MAXN];
bll ans,p[MAXN],f[MAXN][MAXN];
bll dp(int L,int R)//记忆化搜索 
{
	if(f[L][R]!=-1) return f[L][R];
	if(R-L>=1) f[L][R]=max(num[L]*p[k]+dp(L+1,R),dp(L,R-1)+num[R]*p[k]);
	else f[L][R]=num[L]*p[k];
	return f[L][R];
}
void print(bll x)
{
	if(!x) return ;
	if(x) print(x/10);
	putchar(x%10+'0');
}
int main()
{
	in(n);in(m);
	p[0]=1;
	for(int i=1;i<=m;i++) p[i]=p[i-1]*2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		  in(num[j]);
	    memset(f,-1,sizeof(f));
	    ans+=dp(1,m);
	}
	if(!ans) printf("0");
	else print(ans);
	return 0;
}