当前位置: 首页> 游戏> 游戏 > app是怎么开发的_编写程序的步骤_百度拉新推广平台_巨量算数关键词查询

app是怎么开发的_编写程序的步骤_百度拉新推广平台_巨量算数关键词查询

时间:2025/7/9 8:07:27来源:https://blog.csdn.net/GRrtx/article/details/144974210 浏览次数:0次
app是怎么开发的_编写程序的步骤_百度拉新推广平台_巨量算数关键词查询

目录

牛客_宵暗的妖怪_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]);}
}
关键字:app是怎么开发的_编写程序的步骤_百度拉新推广平台_巨量算数关键词查询

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: