intro
题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 \(n\) 的大厦，大厦可以看成由 \(n\) 块宽度为 \(1\) 的积木组成，第 \(i\) 块积木的最终高度需要是 \(h_i\)。
在搭建开始之前，没有任何积木（可以看成 \(n\) 块高度为 \(0\) 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 \([l, r]\)，然后将第 \(L\) 块到第 \(R\) 块之间（含第 \(L\) 块和第 \(R\) 块）所有积木的高度分别增加 \(1\)。
小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。
一个全为 \(0\) 的数组，至少多少次区间加 \(1\) 能加出指定数组。
Sol 1
考虑贪心。
只考虑连续非零段，从左往右考虑：
对于第一个数，显然需要相同次数的区间加，不过这些区间加是可以延续的，就是后面还能用。
接下来考虑第 \(i\) 个数：
- 若 \(a_i>a_{i-1}\)，前面延续下来的区间加都能用，还需要额外以它为起点，补充 \(a_i-a_{i-1}\) 个，且都可以延续。
- 若 \(a_i\le a_{i-1}\)，前面延续的区间就可以满足，不需要新增加操作，但是可延续的区间只剩 \(a_{i}\) 个，剩下的必须在上一位截止，之后不能用了。
全部加起来，答案是 \(a_i-a_{i-1}\) 中所有正数的和。
Sol 2
从差分数组考虑，将区间加改成一个加 \(1\) 一个减 \(1\)，现在只需要凑出原序列的差分数组。
于是考虑将差分数组的正数和负数一一对应，答案就是差分数组里所有正数的和，也就是 \(\Sigma_{i=1}^{n} \max(a_i-a_{i-1},0)\)。
好的，为啥能一一匹配？
因为差分数组的前缀和就是原数组，这玩意恒 \(\ge 0\)，所以任意前缀里 \(+1\) 出现次数大于等于 \(-1\)，视作括号序列就能匹配了。
总结
对于区间加来凑出指定数列的问题，考虑从左往右贪心，或者差分数组。
exercise
1. 区间长度大于 \(1\)
CF1943D1 Counting Is Fun (Easy Version)
给一个长度为 \(n\) 的非负整数序列 \(a_i\)。可以进行若干次操作，每次操作选择一对 \(l,r\) 满足 \(1\leq l<r\leq n\)，将区间 \(a[l,r]\) 都减去 \(1\)。如果一个序列可以通过若干次操作变成全 \(0\) 数列，则我们认为这个数列是好的。
给定 \(n,k,p\)，求所有长度为 \(n\)，值域 \(\in[0,k]\) 的序列有多少个是好的，对 \(p\) 取模。保证 \(p\) 是质数。
\(3\leq n\leq 400, 1\leq k\leq n,\sum n^2\leq 2\times 10^5\)。
赛时没见过这个套路，就往把任意长拆为 \(2\) 和 \(3\) 想。
没做出来，估计这么想就已经毁了，但是不排除是当时自己太菜。
Sol 1
考虑发掘合法数组的性质。
从差分数组考虑：
那么类似于上文，用 \(-1\) 匹配 \(+1\)，但是这次 \(-1\) 只能匹配 \(i-2\) 位及以前的 \(+1\)。
好的，用 Hall 定理判定是否存在完美匹配。
发现枚举子集不必要，应该是枚举每一个前缀，因为不选满 \(+1\) 不会更少。
所以对于任意 \(i\in[2,n]\) 前 \(i\) 位所有减小于等于前 \(i-2\) 位所有加。
化简为 \(i-1\) 位的减和 \(i\) 位的减 \(\le a_{i-2}\)。
要违背这个式子，\(a_{i-1}>a_{i-2}\) 才有可能，发现充要条件就是 \(a_{i-1}\le a_{i}+a_{i+2}\)。
然后用这个式子做枚举前两位的 \(dp\)，前缀和优化即可通过，复杂度 \(n^2k\)。
D2 是其它性质的挖掘，暂时不考虑。
Sol 2
同样：考虑连续非零段。
和上面差不多，但是这里加上对后面一位的限制，为什么呢？
原来（如果 \(a_i>a_{i-1}\)）从这位开始的区间必须延续到下一位。
就能更加容易地得出上面的结论了。
2. 区间必须是前后缀
CF2029G 还没写。
标签：积木,大赛,差分,学习,leq,数组,区间,考虑 From： https://www.cnblogs.com/FunStrawberry/p/18573105