解题思路:
DP
注意事项:
方法二跳过0索引避免出错,不过好像也可以不跳,我不会
参考代码:
方法1:时间复杂度高,容易理解
N = int(input()) maps = [[0 for _ in range(N + 1)] for _ in range(N + 1)] dp = [[[[0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N+1)] for _ in range(N +1)] while 1: nums = list(map(int, input().split())) if sum(nums): maps[nums[0]][nums[1]] = nums[2] else: break for i in range(1, N + 1): for j in range(1, N + 1): for k in range(1, N + 1): for m in range(1, N + 1): temp = maps[i][j] if i == k and j == m else maps[i][j] + maps[k][m] dp[i][j][k][m] = max(dp[i-1][j][k-1][m], dp[i][j-1][k][m-1], dp[i-1][j][k][m-1], dp[i][j-1][k-1][m]) + temp print(dp[-1][-1][-1][-1])
方法2:方法1的优化版本
N = int(input()) maps = [[0 for _ in range(N + 1)] for _ in range(N + 1)] dp = [[[0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + N + 1)] while 1: nums = list(map(int, input().split())) if sum(nums): maps[nums[0]][nums[1]] = nums[2] else: break dp[2][1][1] = maps[1][1] for i in range(2, N + N + 1): for j in range(1, N + 1): for k in range(1, N + 1): temp_0, temp_1 = i - j, i - k if 1 <= temp_0 <= N and 1 <= temp_1 <= N: temp = maps[j][temp_0] if j == k else maps[j][temp_0] + maps[k][temp_1] dp[i][j][k] = max(dp[i-1][j][k-1], dp[i-1][j-1][k], dp[i-1][j][k], dp[i-1][j-1][k-1]) + temp print(dp[-1][-1][-1])
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:605 |
矩形面积交 (C语言代码)浏览:1521 |
【回文数(二)】 (C语言代码)浏览:878 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:560 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2082 |
C语言训练-大、小写问题 (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:343 |
WU-链表数据求和操作 (C++代码)浏览:1331 |
WU-printf基础练习2 (C++代码)浏览:2008 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:551 |