每一行是独立的，分开处理即可。
dp[i][j]表示[i,j]这一段，取完的最大收益。转移很显然,dp[i][j] = max(dp[i + 1][j] + 2^(m - (j - l)) * mp[t][i],dp[i][j - 1] + 2^(m - (j - l)) * mp[t][j])
不想写高精度，python水一发。
1 n,m = map(int,input().split()) 2 res = 0 3 mp = [[0 for i in range(0,80,1)] for i in range(0,80,1)] 4 dp = [[-1 for i in range(0,80,1)] for i in range(0,80,1)] 5 def dfs(t,l,r): 6 if (dp[l][r] >= 0): 7 return dp[l][r] 8 if (l == r): 9 dp[l][r] = int(pow(2,m)) * mp[t][l] 10 return dp[l][r] 11 dp[l][r] = max(dfs(t,l + 1,r) + int(pow(2,m - (r - l))) * mp[t][l],dfs(t,l,r - 1) + int(pow(2,m - (r - l))) * mp[t][r]) 12 return dp[l][r] 13 for i in range(0,n,1): 14 mp[i] = list(map(int,input().split(" "))) 15 for o in range(0,n,1): 16 for i in range(0,m,1): 17 for j in range(0,m,1): 18 dp[i][j] = -1 19 res += dfs(o,0,m - 1) 20 print(res)