动态规划专题

1. 推导公式和结论

题目链接：一道角度推公式的dp题目,相对
题目描述：宽为2长度为m的矩阵，每一个格子有最早能够通过的时间，一个人从（0，0）出发，求每个格子经过一次且走完所有格子需要花费的最少时间。
题目思路：因为要走完所有格子且每个格子仅仅经过一次，所以只能有两种做法。对于每一条路径，发现时间恰好等于该路程上$max(a_i+后面的长度)$, 由于相对性，便可以首先记录后缀的相对最大值，再从前往后统计即可。
就是实现细节比较多。。。

2. 通过数据结构优化

题目链接：双单调队列优化和线段树记录状态
题目描述：对原序列进行划分，是每一份子序列都满足最大值再奇数位置上，最小值再偶数位置上，求所有的划分方案。
题目思路：dp的表达式很好得到，但是如果暴力的复杂度是$O(n^2)$的。对于每一个元素$a_i$考虑维护所有右端点是i的所有区间的最大值和最小值，显然，每次迭代的时候只要更新一个区间内的值，于是可以通过线段树进行维护这部分值。下面就是分类讨论了，对于1位置，对于0位置，分别维护四种状态[0|1,0|1],表示最大值和最小值是在0位置还是在1位置。通识可以使用两个单调队列分别维护需要更新的区间最大值和区间最小值。
小技巧：每个子区间奇数和偶数是相对首位置而言的，为了好维护细节，可以使用0位置表示所有偶数位置，使用1位置表示所有奇数位置。
单调队列可以维护以当前节点为右端点的所有区间的最大值和最小值，同时也可以维护部分区间的最值。

持续更新中。。。。