"#include \n#include \n#include \n\nusing namespace std;\n\nint maxGardeningEfficiency(vector& efficiencies, int K) {\n int N = efficiencies.size();\n vector dp(N + 1, 0); // dp[i]表示以第i只神奇动物结尾的最大园艺效率\n\n dp[1] = efficiencies[0]; // 只有一只神奇动物时,最大园艺效率就是它的效率\n for (int i = 2; i <= N; i++) {\n dp[i] = max(dp[i-1], dp[i-2] + efficiencies[i-1]); // 考虑选择第i只神奇动物或者不选择\n if (i > K)\n dp[i] = max(dp[i], dp[i-K-1] + efficiencies[i-1]); // 如果选择了第i只神奇动物,则前面至少要有K+1只神奇动物不选择\n }\n\n return dp[N];\n}\n\nint main() {\n int N, K;\n cin >> N >> K;\n vector efficiencies(N);\n for (int i = 0; i < N; i++) {\n cin >> efficiencies[i];\n }\n\n int maxEfficiency = maxGardeningEfficiency(efficiencies, K);\n cout << maxEfficiency << endl;\n\n return 0;\n}\n"该代码首先读取输入的神奇动物数量 N 和连续不开心的神奇动物数量 K。然后读取每只神奇动物的园艺效率,并将它们存储在一个向量中。\n\n接下来,使用动态规划算法来计算最大园艺效率。dp[i] 表示以第 i 只神奇动物结尾的最大园艺效率。状态转移方程为:\n\n\ndp[i] = max(dp[i-1], dp[i-2] + efficiencies[i-1])\n\n如果 i > K,则还需要考虑选择第 i 只神奇动物的情况:\n\ndp[i] = max(dp[i], dp[i-K-1] + efficiencies[i-1])\n\n\n最后,输出最大园艺效率。

C++ 代码实现最大花园美化效率:动态规划算法优化

原文地址: https://www.cveoy.top/t/topic/pAxl 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录