宵暗的妖怪

NC213484. 宵暗的妖怪

描述

露米娅作为宵暗的妖怪，非常喜欢吞噬黑暗。

这天，她来到了一条路上，准备吞噬这条路上的黑暗。

这条道路一共被分为 $n\$ 部分，每个部分上的黑暗数量为 $a_i\$ 。

露米娅每次可以任取 连续的 未被吞噬过的三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度。

露米娅想知道，自己能获得的饱食度最大值是多少？

输入描述

第一行一个正整数，代表道路被分的份数。 
第二行有个正整数，代表每一部分黑暗数量。 
数据范围：

输出描述

一个正整数，代表最终饱食度的最大值。

示例1

输入:

7
2 4 1 4 2 1 8

输出:

说明:

选择[2,4,1]和[4,2,1]这两段即可。饱食度为4+2=6。

示例2

输入:

7
2 4 1 7 2 1 8

输出:

说明:

选择[1,7,2]这一段即可。饱食度为7。
值得注意的是，若取两段进行吞噬，反而最多只能获得6的饱食度，并不是最大的。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 46ms, 内存消耗: 1980K, 提交时间: 2022-11-13 20:18:16

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long sum [N],a[N],n;
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(i>2){
			sum[i] = max(sum[i-3]+a[i-1],sum[i-1]);
		}
	}
	cout << sum[n] <<endl;
}

Python3 解法, 执行用时: 191ms, 内存消耗: 15672K, 提交时间: 2022-10-24 18:37:05

n=int(input())
a=list(map(int,input().split()))
ts=[0 for i in range(n)]
ts[2]=a[1]
for i in range(3,n):
    ts[i]=max(a[i-1]+ts[i-3],ts[i-1])
print(ts[-1])

上一题

下一题

详情