每日OJ_牛客_宵暗的妖怪_DP_C++_Java

目次
牛客_宵暗的妖怪_DP
标题剖析
C++代码
Java代码

---

牛客_宵暗的妖怪_DP

宵暗的妖怪
描述：
        露米娅作为宵暗的妖怪，非常喜好吞噬暗中。这天，她来到了一条路上，准备吞噬这条路上的暗中。这条道路一共被分为n 部分，每个部分上的暗中数目为ai​ 。
        露米娅每次可以任取 连续的 未被吞噬过的 三部分，将此中的暗中全部吞噬，并得到中心部分的饱食度。露米娅想知道，自己能得到的饱食度最大值是多少？
输入描述：
   第一行一个正整数n ，代表道路被分的份数。
第二行有n 个正整数ai ，代表每一部分暗中数目。
数据范围：3≤n≤100000,1≤ai≤10^9 
  输出描述：
   一个正整数，代表终极饱食度的最大值。
  

---

标题剖析

打家劫舍，但是别抢到最后一家就行。
打家劫舍问题复习：
Offer必备算法15_简单多问题dp_八道力扣题（打家劫舍+买卖股票）-CSDN博客
以某个位置为末端，结合标题要求，dp 体现：选择到 i 位置时，此时的最大金额。
但是我们这个题在 i 位置的时间，碰面对选择或者不选择两种抉择，所依靠的状态需要细分：
f 体现：选择到 i 位置时， nums 必选，此时的最大金额；
g 体现：选择到 i 位置时， nums 不选，此时的最大金额。
由于状态体现定义了两个，因此状态转移方程也要分析两个：
对于 f ： 如果 nums 必选，那么仅需知道 i - 1 位置在不选的情况下的最大金额， 然后加上 nums 即可，因此 f = g[i - 1] + nums 。
对于 g ： 如果 nums 不选，那么 i - 1 位置上选或者不选都可以。因此，我们需要知道 i - 1 位置上选或者不选两种情况下的最大金额，因此 g = max(f[i - 1], g[i - 1]) 。
C++代码

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. #define int long long
6. signed main()
7. {
8.     int n = 0;
9.     cin >> n;
10.     vector<int> arr(n + 1);
11.     for(int i = 1; i <= n; ++i)
12.     {
13.         cin >> arr[i];
14.     }
15.     vector<int> dp(n + 1);
16.     for(int i = 3; i <= n; ++i)
17.     {
18.         dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]); // 不拿和拿
19.     }
20.     cout << dp[n] << endl;
21.     return 0;
22. }

复制代码

Java代码

1. import java.util.*;
2. public class Main
3. {
4.     public static void main(String[] args)
5.     {
6.         Scanner in = new Scanner(System.in);
7.         int n = in.nextInt();
8.         long[] arr = new long[n + 1];
9.         for(int i = 1; i <= n; i++)
10.         {
11.             arr[i] = in.nextLong();
12.         }
13.         long[] dp = new long[n + 1];
15.         for(int i = 3; i <= n; i++)
16.         {
17.             dp[i] = Math.max(dp[i - 3] + arr[i - 1], dp[i - 1]);
18.         }
20.         System.out.println(dp[n]);
21.     }
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。