c++算法动态规划问题

Question

问题描述

在某个埃及的沙漠中，简·皮耶尔·波鲁纳雷夫(以下简称波波)发现了一个古老的美食餐厅。他发现里面有n种菜品，第

讠种菜的美味度为 ai;。但是由于波波来的实在是太晚了，所以每种菜都只剩下一份了

更不幸的是，这个餐厅被 DI0 的替身 世界 所控制并设下了两个规则:

波波最多只能点k道菜

如果想点笔i种菜，那么波波点的菜必须包含第fai种菜。如果 fai为0，则可以直接点.

但是，波波为了吃到更多的菜，他决定让自己的替身也来点菜。也就是说，波波可以点两次菜，且两次点菜是相互独立

的，但是每种菜一共只能点一次。

在点菜完成后，波波将会大餐一顿，获得所有点的菜的美味度

现在，波波想让你帮他找出两次点菜后能获得的最大美味度，

输入格式

第一行输入两个正整数 n,k

第二行输入 n个整数 fai

第三行输入 n 个整数 ai。

输出格式

波波想让你帮他找出两次点菜后能获得的最大美味度，

样例

输入入数据 1

5 2

0 0 0 0 1
1 2 3 4 5

输出数据 1

13

Answer 1

♥ 该回答参考ChatGPT，由吾为汝整理提供，如若有用，还请题主采纳！♥

这个问题可以通过动态规划来解决。我们需要考虑两次点菜的情况，并且遵循给定的规则。下面是解决这个问题的思路和 C++ 实现。

问题分析

1. 输入参数：

   • n：菜品种类数
   • k：每次最多可以点的菜品数
   • fai：每道菜的依赖关系
   • ai：每道菜的美味度

2. 规则：

   • 如果要点第 i 道菜，必须点第 fai[i] 道菜（如果 fai[i] 为 0，则没有依赖）。
   • 每种菜只能点一次。

3. 目标：

   • 计算两次点菜的最大美味度。

动态规划思路

1. 构建依赖图：使用 fai 数组构建依赖关系。
2. 计算每次点菜的最大美味度：使用动态规划计算在不超过 k 道菜的情况下，能获得的最大美味度。
3. 组合两次点菜的结果：将两次点菜的结果组合，确保没有重复点菜。

C++ 实现

以下是 C++ 的实现代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> fai(n), ai(n);
    for (int i = 0; i < n; i++) {
        cin >> fai[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> ai[i];
    }

    // dp[i][j] 表示选择前 i 道菜，最多选择 j 道菜的最大美味度
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 计算单次点菜的最大美味度
    for (int i = 1; i <= n; i++) {
        int current_fai = fai[i - 1];
        int current_ai = ai[i - 1];

        // 如果有依赖，先计算依赖的美味度
        if (current_fai > 0) {
            current_fai--; // 转换为 0-indexed
            current_ai += ai[current_fai]; // 加上依赖菜的美味度
        }

        for (int j = k; j >= 1; j--) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + current_ai);
        }
    }

    // 计算两次点菜的最大美味度
    int max_taste = 0;
    for (int i = 0; i <= k; i++) {
        max_taste = max(max_taste, dp[n][i]);
    }

    cout << max_taste << endl;

    return 0;
}

说明

1. 输入处理：读取菜品数量、最多点菜数、依赖关系和美味度。
2. 动态规划表：dp[i][j] 表示选择前 i 道菜，最多选择 j 道菜的最大美味度。
3. 依赖处理：在计算美味度时，如果有依赖，则将依赖菜的美味度加上。
4. 结果输出：最后输出两次点菜的最大美味度。

测试样例

输入：

5 2
0 0 0 0 1
1 2 3 4 5

输出：

13

请根据您的需求进行测试和调整。如果有任何问题或需要进一步的帮助，请告诉我！