P1005 矩阵取数游戏

输入

2 3
1 2 3
3 4 2

输出

82

说明/提示
NOIP 2007 提高第三题。

数据范围：

60 % 60\% 60% 的数据满足： 1 ≤ n , m ≤ 30 1\le n,m\le 30 1≤n,m≤30，答案不超过 1 0 16 10^{16} 1016

100 % 100\% 100% 的数据满足： 1 ≤ n , m ≤ 80 1\le n,m\le 80 1≤n,m≤80， 0 ≤ a i , j ≤ 1000 0\le a_{i,j}\le1000 0≤ai,j​≤1000
​
≤1000。
我学python就是为了水高精
思路：

思路来源
不是我的思路，我看这位大佬写的非常详细就截下来了

python天下第一！

matrix=[]

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

for i in range(n):
    row=input().split()
    row=[0]+[int(count)for count in row]+[0]
    #print(row)
    # 把列表塞到列表里形成二维列表
    matrix.append(row)

a=[1]#a[0]=1初始化为1
#求到2^m
for i in range(m):
    a.append(a[i]*2)
    #print(a)
    
ans=0

for i in range(n):
    row=matrix[i]
    w=1
    #分配一个大小为m+2 * m+2的二维数组
    dp=[[0]*(m+2)]*(m+2)
    #print(dp)
    for st in range(1,m+1):
        for ed in range(m,0,-1):
            if ed<st:
                continue
            dp[st][ed]=max(dp[st-1][ed]+row[st-1]*a[m-ed+st-1],dp[st][ed+1]+row[ed+1]*a[m-ed+st-1])
            
    ans+=max([dp[i][i]+row[i]*a[m]for i in range(1,m+1)])
    
print(ans)