T1 史迪仔的晚餐
题目大意
题目给出ttt天，求解在111～ttt天当中，消耗掉的总体的菜的单位。 并且也已经告知了我们每一天的晚上都会消耗掉1单位的菜量。
同时，题目也告诉我们，在给出的第did_idi 天，会进货bib_ibi 个单位的菜量(1个单位的菜量可以供应1个单位的晚饭)。一共有nnn天可以进菜。 现在题目保证进菜的当天一定可以买到菜。
求解ttt天后最多可以吃多少单位的晚饭。
思路模拟
为了去模拟出T天的每天的晚饭的用餐情况，我们可以去枚举出每一天的进货情况与晚饭情况。
1. 枚举出T天当中的每一天
2. 在T天当中，每一天有没有吃饭，有没有进货。
3. T天结束，统计完毕后输出。
伪代码示范
时间复杂度O(n∗t)O(n * t )O(n∗t)
时间复杂度过高，可以对d,bd,bd,b进行对应的优化。
did_idi 的输入顺序是从小往大输入的，也就是说我们枚举当前天数不需要每一次都从头往后枚举
伪代码示范
时间复杂度优化为O(T)O(T)O(T)
题目告诉我们T≤1014T \leq 10^{14}T≤1014，因此我们可以直接否定这样的写法，因为它绝对不可能在一秒之内通过，仅能通过40%的数据样例点。
改变思路
我们可发现，对于题目来说他要求我们去求值的内容为最终的吃掉的晚饭的数量，也就是存在储存单位的区间跨度总和。
而影响是否能吃上饭的数据，其实跟d,bd,bd,b数组有关，而d,bd,bd,b它本身也是处于在TTT天当中的某一天的时间点进行更新的。
假若我们将枚举的对象替换为nnn天的进货天，在进货天当中我们是否可以去枚举出在上一个进货天到下一个进货天的这个区间内的食物呢？
其实思考一下就可以得出来了。
假设我们前一天的进货天为第111天，后一个的进货天为第555天，假设第111天进货了xxx个单位的食物储存。 他在这段时间能够进食的天数为min(x,5−1)min(x,5-1)min(x,5−1)。
因此，枚举每次的进货时间点的方法是可行的。时间复杂也可以被修正为O(n)O(n)O(n)
时间复杂度在O(n)O(n)O(n)
正解代码
T2 - 越野场地布置
题目大意
给出一个具有nnn个顶点的线段，对于线段进行编号，从1,2,3...N1,2,3...N1,2,3...N，初始参数为a1,a2,a3...ana_1,a_2,a_3...a_na1 ,a2 ,a3 ...an 。
你可以选中其中一段连续的子线段[L,R][L,R][L,R],使得这段子线段当中的所有参数进行+1,−1+1,-1+1,−1的操作。
给出线段aaa的所有初始参数，求解最少通过几次上述的操作，可以使其变为另一个给出的线段bbb？
思路解析
想要序列aaa变为序列bbb，求解最小的操作，其中肯定包含一些贪心元素在。
我们可以思考，假如说范围每一次都覆盖很大，很明显对于操作次数来说，只会变多，不会变少，因此我们需要一种策略来进行判断对于哪一段区间进行对应操作。
对于一个顶点来说，他变为另外一个顶点参数的加减方向固定，那么两者之间的差值便是我们对于该顶点的最优操作次数，例如5−>35 -> 35−>3，那么需要对其操作5−35-35−3次。而假若对其进行任何的+1操作，都是增加无效操作的情况。
因此，为了避免这种情况， 我们只需要找到某一段连续的子序列，使其都是上升或者下降在统一进操作，即可为最优解
1. 枚举整个区间
2. 以某一个顶点作为起点，找到另外一个顶点作为终点，使其中的范围的所有数字都是+1，-1的操作
3. 进行加减操作，直到不能在加减为止
枚举贪心的代码长，且难以维护，并且时间复杂还为O(n2)O(n^2)O(n2)及以上。
为了解决此类RMQ的最值问题，我们建议还是采用对应的RMQ算法，例如 前缀和、差分、线段树、树状数组、ST表....
而在这里，我们可以使用差分的性质来解决这个问题。
我们需要确定同号区间范围内的绝对值得额最小值，并且我们需要将多轮加减操作合并为一轮求解对应数值。
这样的区间修改，前缀和差分则是最优解。
我们希望求得高度与当前高度的差分数组，2️⃣原本多个未知的修改在我们的差分数组当中，只需要修改区间的首位两个位置即可。而区间修改的操作仅仅需要O(1)O(1)O(1)。
T3
思路
20% k= 1
这意味着只有右下或者下右两条路线，只需要判断第一行和最后一行，第一列和最后一列是否存在障碍物即可。
40~60%
采用最简单的DFS，可以通过部分的k较小的测试样例。
深搜过程当中，超时的主要原因为在搜索的过程当中，多条路线的某一步会到达同一个顶点。从而造成大量的重复路线的搜索操作。 后续走法明明是相同的。
如果后续走的路线全部都是相同的，那么我们是否可以直接拿之前已经算过的结果直接套用上去。
问题可以转变为，从某一个顶点出发，行走的路线总数继承到达这个顶点的所有路线。当到达终点时，我们就默认这些路线都可以完成，累加上对应的路线总数。
使用动态规划+搜索 -> 记忆化搜索。
T4
思路
每次可以选中一个区间上色，上色的符号为字母A ZA~ZA Z,ASCII越大颜色越深。
涂色的规则为只能在浅色的颜色上去涂更深的颜色。
暴力枚举:
1. 模拟涂色的位置，从前往后一个个看，假如某一个位置与最终结果不符合，那么在执行一次
2. 从当前位置开始，往后涂色到第一个比当前位置颜色浅的位置停下来。
3. 假如后面的颜色比当前深，那么可以进行覆盖前段，反之。
时间复杂度O(n2)O(n^2)O(n2) 。
在中间删除不同区间时，很多地方的涂色其实是在重复计算。
考虑使用前缀和数组记录前面计算过的涂色次数。
后半部分又要重新开始涂色，涂色的过程与前半部分无关，所以会导致前半部分的前缀和到达后半部分时失效。
挖空后半部分的部分，再去计算前缀和。但是这样的话开始起点也会产生对应的变化。
对于一个区间来说，从前往后和从后往前染色的结果最终是一致的。所以后半部分的内容我们可以从维护前缀，变为维护后缀和。
最终答案就变为前后半部分的前缀和+后缀和。
计算前后缀的时候需要注意一下，只会去染色没有出现过的颜色。每次染色的时候都要删除比当前颜色更深的颜色。因为如果为浅色，则与深色前后无法连接。
