首页 > 试题广场 >

种花

[编程题]种花
  • 热度指数：3174 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
公园里有 n 个花园，初始时每个花园里都没有种花，园丁将花园从 1 到 n 编号并计划在编号为 i 的花园里恰好种 Ai 朵花，他每天会选择一个区间 [L，R]（1≤L≤R≤N）并在编号为 L 到 R 的花园里各种一朵花，那么园丁至少要花多少天才能完成计划？

数据范围： ，

输入描述:
第一行包含一个整数 n 。

第二行包含 n 个空格隔开的数 ai 到 an。


输出描述:
输出完成计划所需的最少天数。
示例1

输入

5
4 1 8 2 5

输出

14
示例2

输入

5
1 1 1 1 1

输出

1
算法知识视频讲解
添加回答
Python
Jancydc头像 Jancydc
方法一：动态规划
dp[i]:前i个编号花园里的花最少需要的天数
dp[0] = flowers[0]
状态转移方程：
dp[i]= dp[i-1]                         (flowers[i]<flowers[i-1])
dp[i]=dp[i-1]+flowers[i]-flowers[i-1]  (flowers[i]>=flowers[i-1])
def solution(flowers):
    dp = [0]*len(flowers)
    dp[0] = flowers[0]  # 初始化dp
    for i in range(1, len(flowers)):
        if flowers[i]<flowers[i-1]:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1]+flowers[i]-flowers[i-1]
    return dp[-1]
if __name__ == '__main__':
    n = int(input().strip())
    flowers = list(map(int, input().strip().split()))
    print(solution(flowers))
方法二：贪心，因为相邻的花园可以同时被浇，因此考虑计算相邻的差值，注意不要遗漏数组最后一个数，因为它没有被计算差值 
def solution2(flowers):
    res = []
    for i in range(len(flowers)-1):
        if flowers[i]>flowers[i+1]:
            res.append(flowers[i]-flowers[i+1])
    res.append(flowers[-1])
    return sum(res)

if __name__ == '__main__':
    n = int(input().strip())
    flowers = list(map(int, input().strip().split()))
    print(solution2(flowers))
发表于 2020-06-26 13:24:05 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 美团 2019 Java工程师
来自：美团2019年秋招部分...
上传者：小小
难度：
2条回答 8825浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号