?題目鏈接：

宵暗的妖怪

?題目描述?

• 露米婭作為宵暗的妖怪，非常喜歡吞噬黑暗。
• 這天，她來到了一條路上，準備吞噬這條路上的黑暗。
• 這條道路一共被分為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]
• 狀態轉移方程：應該選擇兩種情況的最大值

1. 選擇綠色區間時dp[i]=dp[i-3]+v[i-1]
2. 選擇藍色區間時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;
}

---

※ 如果文章對你有幫助的話，可以點贊收藏！！謝謝支持