@[TOC]
题目传送门
https://www.lanqiao.cn/problems/2355/learning/?contest_id=79
问题描述
小蓝正在设计一个排水管道的工程，将水从西边一个离地面很高的水库引到东边的地面。
为了项目更有艺术性，小蓝建造了很多高低不同的的柱子用于支撑流水的水槽，柱子之间的间距相同。
当西边的柱子比东边相邻的柱子至少高 1 时，水能正常通过水槽向东流，否则可能出现异常。
但是，小蓝发现施工方建造的柱子是忽高忽低的，不满足西边高东边低的要求。小蓝不得不修改柱子的高度以便水能正常通过水槽。同时，小蓝需要用 上所有的柱子，最东边的柱子高度至少为 1，最西边的柱子高度可以为任意高度。每修改一根柱子的高度，需要花费 1 的代价（不管高度改变多少代价都是 1）。
请问，小蓝最少花费多大的代价，可以让水能正常通过所有水槽？在修改时，小蓝只会把柱子的高度修改为整数高度。
输入格式
输入的第一行包含一个整数 n，表示柱子的数量。
第二行包含 n 个整数 h1 , h2 , ···, hn，从西向东表示每根柱子的高度。
输出格式
输出一行包含一个整数，表示答案。
样例输入
6 8 9 5 2 1 1
样例输出
3
样例说明
至少修改三根柱子，高度变为 8,7,5,3,2,1。
评测用例规模与约定
对于 30% 的评测用例，2 ≤ n ≤ 100，1 ≤ hi ≤ 100 。 对于 60% 的评测用例，2≤n≤1000，1≤hi≤10000。 对于所有评测用例，2 ≤ n ≤ 100000，1 ≤ hi ≤ 10^9。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
难度: 简单 标签: 省赛, 2020
LIS 的一般做法
首先这题给人的第一印象就是求下降子序列的最大长度，但是一般的动规只能达到O(n²)
code
n = int(input()) a = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n-1): for j in range(i+1, n): if n-j <= a[j] <= a[i]+i-j: dp[j] = max(dp[j], dp[i]+1) # 经典动规，如果i能到j就考虑是否要将j接到i后面 print(n-max(dp))
LIS的优化做法
很简短，但是不能AC，TLE了四个点，所以有大佬提出了O(nlogn)的优化，即dp[i]不再表示到 i 的最长子串长度了，而是表示以 i 结尾的子串，再单独由ans变量来存储长度，之所以从n到logn是因为多了一个单调数组，可以运用二分。
code
import bisect # python的二分库 n = int(input()) a = tuple(zip(map(int, input().split()), range(n))) for i0, j0 in a: # 将第一个符合条件的筛出 if i0 >= n: dp = [(i0, j0)] break ans = 1 for i, j in a: if n-j <= i and j > j0: if i <= dp[-1][0]+dp[-1][1]-j: dp.append((i, j)) ans += 1 else: if i > i0: dp[0] = (i, j) else: m = bisect.bisect_left([k[0] for k in dp], i) if i <= dp[m-1][0]+dp[m-1][1]-j: dp[m] = (i, j) print(n-ans)
但是上面的代码是有误的，而且有很大的漏洞，因为我们需要快速搜索所取数的下标，因为有重复数据所以难以实现，就算实现了也会损失空间或者效率。接下来看看AC正解。
正确思路
理解了这些储备知识，就来到了这题的关键：什么叫西边比东边高，最东边至少得是1 。
- 1. 这里的条件首先可以归纳为从右边的1开始，每个至少得是2，3，4...那么用程序来表达就是条件1：值和下标相加至少是原数组的长度n
- 2. 但是这样还是不够的，因为如果要向原下降子序列里添加新的一项，要确保两项中间的所有数都能被合规修改，如数组4，2，3，1. 虽然4 和 3 都满足了至少是n的条件，但是3不能添加进递减数列，因为4和3中间还有一个数是没办法修改的，那么我3们就得到下一个数 j 和前一个数 i 必须满足条件2： j <= i + i下标-j下标
- 3. 条件已经凑齐了，但是可以直接开始做了吗？还是不行，直接开始就是上面的错误代码，还是避不开下标的搜索，那么还可以怎么简化呢？
- 4. 可以对条件2进行移项：j+j下标 <= i+i下标，那么我们将值和下标绑定，直接对它们的和进行求不上升子序列不就行了吗？
- 所以条件都集齐了，可以开始AC咯
正确code
def check(x, key): # 手打二分，注意bisect不好使了，因为前面两个要手动添加才能传递是上升 还是下降 l = 0 r = len(x)-1 while l < r: # 选取这种2分是因为nlogn做法的性质，如果有疑问可以去百度一下最长上升子序列的优化 m = l+r >> 1 if x[m] >= key: l = m+1 else: r = m return r n = int(input()) a = zip(map(int, input().split()), range(n)) # 对值和下标进行打包 a = [i+j for i, j in a if i+j >= n] # 绑定并手动过滤 b = [] # 存nlogn形式的dp ans = 0 # 存不上升子序列的长度 for i in a: if not b or i <= b[-1]: b.append(i) ans += 1 else: b[check(b, i)] = i print(n-ans)
