原题
春春是一名道路工程师，负责铺设一条长度为 
的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 块首尾相连的区域，一开始，第 块区域下陷的深度为 。
春春每天可以选择一段连续区间 ，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。
输入描述：
输入包含两行，第一行包含一个整数 ，表示道路的长度。
第二行包含 个整数，相邻两数间用一个空格隔开，第 个整数为 。
其中， 。
输出描述：
输出仅包含一个整数，即最少需要多少天才能完成任务。
分析
将道路分为n段，编号分别为0, 1, 2, ... , n-1，每段道路有一定深度的坑，现在需要每天选择一段尽可能长的路段区间，且路段区间内的坑的深度不为0（贪心策略），然后对该路段区间进行“填坑”。
- 首先选择最大区间 [0, n-1]，求当前区间最小值m
- 找到第一个m所在的位置i，以此为分裂点将区间分裂成两个区间，对这两个区间进行“选择”
- 则当前区间为选择的一段尽可能长的路段区间
- 对该区间进行“填坑”，连续填坑m天
- 此时该区间出现坑的深度不为0的路段，需要递归地选择该区间（将分裂该区间）
源码
n = int(input())
depth = [int(i) for i in input().split()]
# 测试数据1,输出：9
# n = 6
# depth = [4, 3, 2, 5, 3, 5]
days = 0
def tiankeng(start_i,end_i):
global days
if start_i >= end_i:
return
m = min(depth[start_i:end_i])
# 若当前区间最小值为0，需要进行区间分裂
if m == 0:
# 分裂点为第一个0元素所在的位置
for i in range(start_i,end_i):
if depth[i] == 0:
tiankeng(start_i,i)
tiankeng(i+1,end_i)
break
# 若当前区间最小值不为0，即当前路段区间没有深度为0的坑，则进行填坑
else:
days += m
depth[start_i:end_i] = [ e-m for e in depth[start_i:end_i] ]
tiankeng(start_i,end_i)
tiankeng(0,n)
print(days)
上一篇：蓝桥杯备战日志(Python)14-数列求值&七段码-(枚举、取余&连通图与其子图)
