矩阵取数游戏

这里我们推一下这个题的精髓：
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]假定某一行有两个数x,y;
那么我们有两种选择：
先拿x，再拿y：x*2+y*4；
先拿y，再拿x：y*2+x*4；定义di为第i次取数，第一次取数记为d1，第二次d2……
那么上面的情况可以这样表示：2*d1+4*d2;
提一个2出来：2*(d1+2*d2)
发现了没，式子里只有2！推广得到，一行有n个数：
n=3: 2*(d1+ 2*(d2+ 2*d3))
n=4: 2*(d1+ 2*(d2+ 2*(d3+ 2*d4))
n=5: 2*(d1+ 2*(d2+ 2*(d3+ 2*(d4+ 2*d5)))
^-^
菜菲不会表达了，但你肯定能意会到<比心>

python:
数组b计算需要强转

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]#从下标1开始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-1dp[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)