第三题没思路，只会暴力，感觉2e9绝对没希望，就直接放弃了
第四题，题目大致是有一个矩阵，在部分位置(i,j)有宝藏价值v，有两个人从(0,0)走到(m, n)，（i，j)处宝藏只能被一个人拿走，每个人每次只能向右方或下方走一个单位，如何让两个人的宝藏价值之和最大。。。
我的思路是：一个人先走，他走完了，另一个再走（相当于一个人他从起点->终点->起点），类似一个“闭环”，但是可以重叠，但是就过了60%例子，感觉思路有点错，有无大佬指点下
屎山如下：
m, n, k = list(map(int, input().split()))
stones = {}
for i in range(k):
x, y, v = list(map(int, input().split()))
stones[(x - 1, y - 1)] = v
dp = [[0] * n for _ in range(m)]
if (0, 0) in stones:
dp[0][0] = stones[(0, 0)]
for i in range(1, n):
dp[0][i] = dp[0][i - 1] + stones.get((0, i), 0)
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + stones.get((i, 0), 0)
for i in range(1, m):
for j in range(1, n):
if (i, j) in stones:
dp[i][j] = max(dp[i - 1][j] + stones[(i, j)], dp[i][j - 1] + stones[(i, j)])
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = dp[-1][-1]
x, y = m - 1, n - 1
while x != 0 or y != 0:
for _x, _y in [(-1, 0), (0, -1)]:
if 0 <= x + _x < m and 0 <= y + _y < n and dp[x + _x][y + _y] + stones.get((x, y), 0) == dp[x][y]:
if (x, y) in stones:
stones.pop((x, y))
x = x + _x
y = y + _y
# print(stones)
# 2nd part
dp = [[0] * n for _ in range(m)]
for i in range(1, n):
dp[0][i] = dp[0][i - 1] + stones.get((0, i), 0)
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + stones.get((i, 0), 0)
for i in range(1, m):
for j in range(1, n):
if (i, j) in stones:
dp[i][j] = max(dp[i - 1][j] + stones[(i, j)], dp[i][j - 1] + stones[(i, j)])
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
temp_res = dp[-1][-1] + res
print(temp_res)
评论 (16)
