NC16645 矩阵取数游戏(记忆化搜索)

题目链接

题意：




题解：











AC代码

f = [[0 for i in range(100)] for i in range(100)]
n, m = map(int, input().split())
a = [0 for i in range(100)]
def dfs(l, r) :
    len = r - l + 1
    x = m - len + 1
    if f[l][r] :
        return f[l][r]
    if l == r :
        return a[l] * (2 ** x)
    f[l][r] = max(dfs(l + 1, r) + a[l] * 2 ** x, dfs(l, r - 1) + a[r] * 2 ** x)
    return f[l][r]

ans = 0
for i in range(n):
     f = [[0 for i in range(100)] for i in range(100)]
     a = list(map(int, input().split()))
     ans += dfs(0, m - 1)
print(ans)