本文主要是介绍【算法】宵暗的妖怪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
✨题目链接：
宵暗的妖怪
✨题目描述
- 露米娅作为宵暗的妖怪，非常喜欢吞噬黑暗。
- 这天，她来到了一条路上，准备吞噬这条路上的黑暗。
- 这条道路一共被分为n 部分，每个部分上的黑暗数量为ai 。
- 露米娅每次可以任取 连续的 未被吞噬过的 三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度。
- 露米娅想知道，自己能获得的饱食度最大值是多少？
✨输入描述:
- 第一行一个正整数n ，代表道路被分的份数。
- 第二行有n 个正整数ai ，代表每一部分黑暗数量。
- 数据范围：3≤n≤100000,1≤ai≤10^9
✨输出描述:
一个正整数，代表最终饱食度的最大值。
✨示例1
📍输入
7
2 4 1 4 2 1 8
📍输出
6
📍说明
选择[2,4,1]和[4,2,1]这两段即可。饱食度为4+2=6。
✨示例2
📍输入
7
2 4 1 7 2 1 8
📍输出
7
📍说明
选择[1,7,2]这一段即可。饱食度为7。
值得注意的是，若取两段进行吞噬，反而最多只能获得6的饱食度，并不是最大的。
✨解题思路
线性dp：
- 状态表示：dp[i]表示从 [1,i] 区间内吞噬黑暗，最大的饱食度
- 返回值：dp[n]
- 状态转移方程：应该选择两种情况的最大值
- 选择绿色区间时dp[i]=dp[i-3]+v[i-1]
- 选择蓝色区间时dp[i]=dp[i-1]
✨代码
#include <iostream>
#include <vector>
using namespace std;typedef long long ll;int main()
{int n;cin >> n;vector<ll> v(n + 1);vector<ll> dp(n + 1);for (int i = 1; i <= n; i++){cin >> v[i];if (i >= 3){dp[i] = max(dp[i - 3] + v[i - 1], dp[i - 1]);}}cout << dp[n] << endl;return 0;
}
※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持
这篇关于【算法】宵暗的妖怪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
