关于#C++动态规划#的问题,如何解决?

Question

希望能帮忙解决一下今天不会的题(应该是动态规划):

最好是C++的代码加上思路!谢谢

Answer 1

这是一道动态规划题目。

我们可以使用自底向上的方法来求解这道题目。

首先我们可以定义一个数组dp[i]表示到第i个时间结点的最大收获。

具体来说，我们可以从小到大循环每个时间结点i，对于每个时间结点i，我们可以循环每个指向它的时间结点j，如果有多个指向它的时间结点j，则取收获最大的那个即可。

最终结果就是dp[n]，即最后一个时间结点的最大收获值。

具体代码如下：

int n;
int v[MAX_N];
int f[MAX_N];
int dp[MAX_N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> f[i];

    for (int i = n; i >= 1; i--)
    {
        if (f[i] == 0) dp[i] = v[i];
        else
        {
            dp[i] = v[i];
            for (int j = f[i]; j != 0; j = f[j]) dp[i]