首页 > 试题广场 >

种花

[编程题]种花

热度指数：3197 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $1 \le n \le 10^5 \$ ， $0 \le A_i \le 10^4 \$

输入描述:

第一行包含一个整数 n 。

第二行包含 n 个空格隔开的数 a_i 到 a_n。

输出描述:

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

示例1

输入

5
4 1 8 2 5

输出

示例2

输入

5
1 1 1 1 1

输出

算法知识视频讲解

17c89

发表于 2024-01-22 12:32:50

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

laglangyue

发表于 2020-06-19 22:32:28

贪心+暴力模拟，100%由第一种方法可以产生一种递归方法，以最小点分割数组，递归两个子数组，递归只能过65%。如下代码：注释中为贪心+模拟，最佳思路：递增数组(评论区大佬) package org.niuke.solution78; import java.util.ArrayList; impo 展开全文