C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 708K, 提交时间: 2020-07-07 09:51:38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
int t,n,m;
lll dp[100][100];
lll ans=0;
void print(__int128 x)
{
    if (x>9) print(x/10);
    putchar('0'+x%10);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=m;j++){
            scanf("%d",&dp[j][j]);
        }
        for(int j=1;j<m;j++){
            for(int k=1;k<=m-j;k++){
                dp[k][j+k]=max(dp[k+1][j+k]*2+dp[k][k],dp[k][j+k-1]*2+dp[j+k][j+k]);
            }
        }
        ans+=dp[1][m]*2;
    }
    print(ans);
}

C++ 解法, 执行用时: 6ms, 内存消耗: 504K, 提交时间: 2021-06-08 18:51:33

#include<bits/stdc++.h>
using namespace std;
inline void print(__int128 x)
{
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
__int128 DP[85][85],ans=0;
int main()
{
    int i,j,k,len,n,m,a[85][85];
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    	for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++) DP[j][j]=a[i][j];
		for(len=2;len<=m;len++)
			for(j=1,k=j+len-1;k<=m;j++,k++)
			    DP[j][k]=max(DP[j+1][k]*2+a[i][j],DP[j][k-1]*2+a[i][k]);
		ans+=DP[1][m]*2;
	}
	print(ans);
	return 0;
}

pypy3 解法, 执行用时: 200ms, 内存消耗: 49068K, 提交时间: 2021-07-14 13:55:16

if __name__ == '__main__':
    n, m = map(int, input().split(' '))
    ans = 0
    for T in range(n):
        f = [[0 for j in range(m+1)] for i in range(m+1)]
        a = list(map(int, input().split(' ')))
        s1 = 0
        while s1 < m:
            s2=0
            while s2+s1 < m:
                i = s2
                j = s1+s2

                f[i][j] = max(f[i+1][j]+2**(m-s1)*a[i], f[i][j-1]+2**(m-s1)*a[j])

                s2 += 1

            s1 += 1
        ans+=f[0][m-1]
    print(ans)

Python3 解法, 执行用时: 594ms, 内存消耗: 5468K, 提交时间: 2023-06-28 14:59:52

n,m=map(int,input().split())

b=[[]for i in range(2005)]
for i in range(n):
    b[i]=input().split()
    b[i]=[0]+b[i]
 
ans=0
for c in range(n):
    dp=[[0 for j in range(85)]for i in range(85)];
    for len in range(1,m+1):
        for i in range(1,m-len+2):
            j=i+len-1
            dp[i][j]=max(int(b[c][i])+dp[i+1][j],dp[i][j-1]+int(b[c][j]))
            dp[i][j]=2*dp[i][j]
    ans=ans+dp[1][m]

print(ans)