种花

　

种花

岛屿沉没问题

牛客网：种花

题目描述

公园里有N个花园，初始时每个花园里都没有种花，园丁将花园从1到N编号并计划在编号为i的花园里恰好种A_i朵花，他每天会选择一个区间[L，R]（1≤L≤R≤N）并在编号为L到R的花园里各种一朵花，那么园丁至少要花多少天才能完成计划？

输入描述:

第一行包含一个整数N，1≤N≤10^5。

第二行包含N个空格隔开的整数A_1到A_N，0≤A_i≤10^4。

输出描述:

输出完成计划所需的最少天数

示例1

输入

5

4 1 8 2 5

输出 14

这个种花问题好比是岛屿沉没问题。我们以例子来分析整个过程：

1 首先 所有花园都种当前所需数目最少的花，$stack=\left[1\right]$stack=[1] ，此时的花园是$[3,0,7,1,4]$[3,0,7,1,4]；

2 接着花园由0被分为两块单独种植，左边的是 $\left[3\right]$[3]，左边一次种3朵；右边的是 $[7,1,4]$[7,1,4]，右边的花园一次种当前所需数目最小的花，就是1朵。因此 $stack=[1,3,1]$stack=[1,3,1]，花园变成了 $[0,0,6,0,3]$[0,0,6,0,3]；

3 最后直接统计 $stack=[1,3,1,6,3]$stack=[1,3,1,6,3]。那么stack的求和就是答案。

注意到，stack中的第一个3，来自于4和1的做差；stack中的6，来自于8和2的作差，余下的3以及两个1（余下的元素），恰好就是变化的花园最后一个最高山峰元素的分解（请注意用词是最后一个山峰）。那么是否对所有的情况都可以如此分析呢？

比如 $[5,4,3,2,1]$[5,4,3,2,1]，$[1,3,8,6,4,9]$[1,3,8,6,4,9]，$[1,3,8,6,4,9,2]$[1,3,8,6,4,9,2] ，自行验证。

原理是什么呢？岛屿会沉没，山的高度会变，但是相邻山的高度差是永恒不变的，这个差值一定会被累加上。而刚刚提过的最后一个山峰的分解，我相信很多人都可能不理解，没关系，我们可以这么想。数组构成了好多个山峰，我们只统计前面的山峰高度差，保留最后一个山峰的峰值，那么求和就是答案。比如示例，就是 3+6+5=14，比如$[1,3,8,6,4,9]$[1,3,8,6,4,9]，就是 2+2+9=13，比如$[1,3,8,6,4,9,2]$[1,3,8,6,4,9,2] ，就是 2 +2 +9=13。

再比如 $[5,2,8,1,4]$[5,2,8,1,4]，3+7+4=14，比如$[9,4,6,8,3,1]$[9,4,6,8,3,1]，就是 5 + 8 = 13，再比如$[2,9,4,6,8,3,1]$[2,9,4,6,8,3,1]，就是 5 + 8 =13。

看到我举的例子了吗？其实我后面举的例子就是之前例子的翻转，也就是说，这些岛屿（所需花朵）沉没的时候不论是从左到右还是从右到左观察，得到的结果应该都是相同的。那么代码中给出的是从左到右遍历的结果，其实从右到左也是可以的。

另外本题因此可以分解成子问题，所以递归也可以。可是复杂度有些高，无法通过。

if __name__=='__main__':
    n = int(input())
    num = list(map(int,input().split()))
    count = 0
    for i in range(n-1):
        count += max(num[i]-num[i+1],0)
    print(count+num[-1])

相关阅读

种花家是什么意思？

充满鲜花的世界到底在哪里，如果它真的存在那么我一定会去。

微信改版后头图怎么做？这种花式玩法终于可以彻底玩了!

上周，微信进行了逆天大改版：改版后订阅号群发的图文消息将直接出现在于服务号同级的“订阅号消息”栏。图文消息按照推送的时间顺序