题解 | #矩阵取数游戏#

解题思路：

• 行之间是独立的，取数时可以单行考虑，令$d{p}_{l,r}dp\_\{l,r\}$表示当前行从左取的个数和从右取的个数所得到的得分值。则$d{p}_{l,r}fromd{p}_{l-1,r}ord{p}_{l,r-1}dp\_\{l,r\}\; \backslash \; from\; \backslash \; dp\_\{l-1,r\}\; \backslash \; or\; \backslash \; dp\_\{l,r-1\}$取最大值即可。
• $d{p}_{l,r}=\max (d{p}_{l,r},d{p}_{l-1,r}+v_l\ast 2^i,d{p}_{l,r-1}+v_r\ast 2^i)dp\_\{l,r\}\; =\; \backslash max(dp\_\{l,r\},\; dp\_\{l-1,r\}\; +\; v\_l\; *\; 2^i,\; dp\_\{l,r-1\}\; +\; v\_r\; *\; 2^i)$
• 数据涉及高精度计算，这里跳过高精度直接利用python的高精度计算

n,m = map(int, input().split())
ans = 0
for i in range(n):
    lst = list(map(int, input().split()))#输入一行处理一行结果汇总
    dp = [[0] * (m+1) for j in range(m+1)]
    for ln in range(1,m+1): #枚举取数长度
        for l in range (ln+1): #枚举构成这个长度的每一种组合
            r = ln - l
            if l > 0:
                dp[l][r] = (dp[l-1][r] + lst[l-1] * 2**ln)
            if r > 0:
                dp[l][r] = max((dp[l][r-1] + lst[m-r] * 2**ln), dp[l][r])
    mx = 0
    for l in range(m+1): #取各组合最大值
        mx = max(dp[l][m-l], mx)
    ans += mx #合并答案
    ans %= 1000000007
print(ans)