4006. 数组推导
摘要
Title: 4006. 数组推导
Tag: 贪心
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
4006. 数组推导
-
题意
A1,A2,⋯,An 是一个由 n 个自然数（即非负整数）组成的数组。
在此基础上，我们用数组 B1⋯Bn 表示 A 的前缀最大值。
Bi=max{A1,A2,⋯,Ai}
如上所示，Bi 定义为数组 A 中前 i 个数的最大值。
根据该定义易知 A1=B1，且随着 i 的增大，Bi 单调不降。
此外，我们用 sum=A1+A2+⋯+An 表示数组 A 中 n 个数的总和。
现已知数组 B，我们想要根据 B 的值来反推数组 A。
显然，对于给定的 B，A 的取值可能并不唯一。
试计算，在数组 A 所有可能的取值情况中，sum 的最大值和最小值分别是多少？ -
思路
最大的：原数组的和
最小的：连续相同子串出现时，将其合并为一个数 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21'''
Author: NEFU AB-IN
Date: 2022-03-16 17:34:03
FilePath: \ACM\Acwing\4006.py
LastEditTime: 2022-03-16 17:34:04
'''
N = 110
nums = [0] * N
n = int(input())
nums[1:] = list(map(int, input().split()))
print(sum(nums))
ans = 0
for i in range(1, n + 1):
if nums[i] == nums[i - 1]:
ans -= nums[i]
ans += nums[i]
print(ans)