瓦罗兰大陆c++求解

Question

描述

欢迎来到瓦罗兰大陆，该大陆包括:德玛西亚、诺克萨斯、弗雷尔卓德…等，一共有 N 个区域，每个区域均有且仅有一个传送阵，但是传送阵只能通往一个区域，每个区域有一个 LOL 战力，第 i 个区域的 LOL 战力为 A
i
​
。

小星非常想知道，从第 i 个区域出发，并只通过传送阵前往下一个区域，LOL 战力之和最多是多少（到达一个区域多次只计算 1 次 LOL 战力）。

输入描述
第一行为一个正整数 N。

第二行有 N 个非负整数 A
i
​
，表示了每个区域的 LOL 战力

第三行有 N 个正整数 L
i
​
，表示通过第 i 个区域的传送阵所到达的区域为 L
i
​
，可能出现 L
i
​
=i 的情况。

输出描述
输出 N 行，第 i 行为一个非负整数，表示从第 i 个区域出发，LOL战力之和的最大值为多少。

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题分析： 这是一个经典的动态规划问题，我们可以用 DP 数组来记录从每个区域出发的最大 LOL 战力之和。DP 数组的定义为：DP[i] 表示从第 i 个区域出发的最大 LOL 战力之和。 我们可以从后往前依次计算每个 DP 值，如果当前区域的传送阵可以到达多个区域，我们需要在这些区域中选择一个 LOL 战力最大的区域。具体的，我们可以用一个 max_lol 变量来记录当前区域可以到达的区域中最大的 LOL 战力，然后更新 DP 值即可。 代码实现： 时间复杂度是 O(N^2)，空间复杂度是 O(N)。

n = int(input())
lol = list(map(int, input().split()))
links = list(map(int, input().split()))
dp = [0] * n
for i in range(n-1, -1, -1):
    if links[i] == i:
        dp[i] = lol[i]
    else:
        max_lol = 0
        for j in range(i+1, n):
            if links[j] == i:
                max_lol = max(max_lol, dp[j])
        dp[i] = lol[i] + max_lol
for i in range(n):
    print(dp[i])