目錄

牛客_宵暗的妖怪_DP

題目解析

C++代碼

Java代碼

---

牛客_宵暗的妖怪_DP

宵暗的妖怪

描述：
????????露米婭作為宵暗的妖怪，非常喜歡吞噬黑暗。這天，她來到了一條路上，準備吞噬這條路上的黑暗。這條道路一共被分為n 部分，每個部分上的黑暗數量為ai??。

????????露米婭每次可以任取 連續的 未被吞噬過的 三部分，將其中的黑暗全部吞噬，并獲得中間部分的飽食度。露米婭想知道，自己能獲得的飽食度最大值是多少？

輸入描述：

第一行一個正整數n ，代表道路被分的份數。
第二行有n?個正整數ai?，代表每一部分黑暗數量。
數據范圍：3≤n≤100000,1≤ai≤10^9?

輸出描述：

一個正整數，代表最終飽食度的最大值。

---

題目解析

打家劫舍，但是別搶到最后一家就行。

打家劫舍問題復習：

Offer必備算法15_簡單多問題dp_八道力扣題（打家劫舍+買賣股票）-CSDN博客

以某個位置為結尾，結合題目要求，dp[i] 表示：選擇到 i 位置時，此時的最大金額。

但是我們這個題在 i 位置的時候，會面臨選擇或者不選擇兩種抉擇，所依賴的狀態需要細分：

f[i] 表示：選擇到 i 位置時， nums[i] 必選，此時的最大金額；
g[i] 表示：選擇到 i 位置時， nums[i] 不選，此時的最大金額。
因為狀態表示定義了兩個，因此狀態轉移方程也要分析兩個：

對于 f[i] ： 如果 nums[i] 必選，那么僅需知道 i - 1 位置在不選的情況下的最大金額， 然后加上 nums[i] 即可，因此 f[i] = g[i - 1] + nums[i] 。
對于 g[i] ： 如果 nums[i] 不選，那么 i - 1 位置上選或者不選都可以。因此，我們需要知道 i - 1 位置上選或者不選兩種情況下的最大金額，因此 g[i] = max(f[i - 1], g[i - 1]) 。

C++代碼

#include <iostream>
#include <vector>
using namespace std;
#define int long longsigned main()
{int n = 0;cin >> n;vector<int> arr(n + 1);for(int i = 1; i <= n; ++i){cin >> arr[i];}vector<int> dp(n + 1);for(int i = 3; i <= n; ++i){dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]); // 不拿和拿}cout << dp[n] << endl;return 0;
}

Java代碼

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();long[] arr = new long[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextLong();}long[] dp = new long[n + 1];for(int i = 3; i <= n; i++){dp[i] = Math.max(dp[i - 3] + arr[i - 1], dp[i - 1]);}System.out.println(dp[n]);}
}