Day64力扣打卡

打卡记录

方格取数（线性DP）

import sys
input = sys.stdin.readline

'''
输入样例：
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例：
67
'''

n = int(input())
w = [[0] * (n + 1) for _ in range(n + 1)]
while True:
    a, b, c = map(int, input().split())
    if a == 0 and b == 0 and c == 0:
        break
    w[a][b] = c
f = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(2 * n + 1)]
for k in range(2, 2 * n + 1):
    for i1 in range(1, n + 1):
        for i2 in range(1, n + 1):
            j1, j2 = k - i1, k - i2
            if 1 <= j1 <= n and 1 <= j2 <= n:
                t = w[i1][j1]
                if i1 != i2:
                    t += w[i2][j2]
                f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2]) + t
print(f[-1][-1][-1])