解题思路:
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语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:572 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:543 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:667 |
完数 (C语言代码)浏览:685 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:664 |
1025题解浏览:732 |
川哥的吩咐 (C语言代码)浏览:609 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1181 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:556 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言描述——递归算法)浏览:1120 |