($nm^2$)60pts

区间动态规划

每一行都是独立的，因此每行可以分别算最大值。 在每一行内: 状态表示:$f[i,j]$表示将$[i，j]$这段数取完的所有取法的最大分值。

状态计算:将 $f[i,j]$所表示的所有取法分成两类:

先取左端点：这一类的最大分值是 $f[i+ 1,j]+ w[i] \times 2^{m-j+i}$，其中 $w[i]$ 是第 $i$ 个数的值。

先取右端点。这一类的最大分值是 $f[i,j-1]+ w[j] \times 2^{m-j+i}$，其中 $w[j]$ 是第 $j$ 个数的值。

则 $f[i,j]$,就是这两类的较大值。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=85;
LL f[N][N];
LL w[N][N];
LL n,m;
LL work(LL w[])
{
    for(int len=1;len<=m;len++) //枚举长度
    {
        for(int i=1;i+len-1<=m;i++) //枚举左端点
        {
            int j=i+len-1; //右端点
            int t=m-j+i; //第几次取(右边的数+左边的第几个数)
            f[i][j]=max(f[i+1][j]+w[i]*(1ll<<t),f[i][j-1]+w[j]*(1ll<<t));
        }
    }
    return f[1][m];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++) //枚举每行
    {
        res+=work(w[i]);
    }
    cout<<res;
    return 0;
}

$nm^2\ 100pts$

高精度+区间动态规划

#include<bits/stdc++.h>
using namespace std;
const int N=85,M=31;
int n,m;
int w[N][N];
int f[N][N][M];
int p[N][M];
int ans[M];
void mul(int a[],int b[],int c) //高精度乘法 
{
	int tmp[M]={};
	for(int i=0,t=0;i<M;i++)
	{
		t+=b[i]*c;
		tmp[i]=t%10;
		t/=10;
	}
	memcpy(a,tmp,M*4);
}
void add(int a[],int b[],int c[]) //高精度加法 
{
	int tmp[M]={};
	for(int i=0,t=0;i<M;i++)
	{
		t+=b[i]+c[i];
		tmp[i]=t%10;
		t/=10;
	}
	memcpy(a,tmp,M*4);
}
int compare(int a[],int b[]) //高精度比较 
{
	for(int i=M-1;i>=0;i--)
	{
		if(a[i]>b[i]) return 1;
		else if(a[i]<b[i]) return -1;	
	}	
	return 0;
} 
void work(int w[])
{
	int a[M],b[M];
	for(int len=1;len<=m;len++)
	{
		for(int i=0;i+len-1<m;i++)
		{
			int j=i+len-1;
			int t=m-j+i;
			mul(a,p[t],w[i]),mul(b,p[t],w[j]); //左右的数值 
			add(a,a,f[i+1][j]); //累加右边区间 
			add(b,b,f[i][j-1]); //累加左边区间 
			if(compare(a,b)>0) //储存最大值 
			{
				memcpy(f[i][j],a,M*4);
			}
			else
			{
				memcpy(f[i][j],b,M*4);
			}
		}
	}
	add(ans,ans,f[0][m-1]); //累加答案 
} 
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>w[i][j];
		}
	}
	p[0][0]=1; //计算2^i次方 
	for(int i=1;i<=m;i++)
	{
		mul(p[i],p[i-1],2);
	}
	for(int i=0;i<n;i++) //计算每一行 
	{
		work(w[i]);
	}
	int lenc=M-1; //高精度输出模板 
	while(lenc&&ans[lenc]==0) lenc--;
	for(int i=lenc;i>=0;i--)
	{
		cout<<ans[i];
	}
	return 0;
}