把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

有n头狼排成一排，每只狼都对相邻的狼的攻击力有加成作用，每杀死一只狼所受到的伤害为当前狼的攻击力（算上加成的部分），被杀死后的狼对相邻的狼的攻击力的加成会被取消，同时，原先与被杀死的相邻的两头狼会变成相邻的狼。要求使得受到的伤害值最小，求出最小值。

解：

a[i]表示第i头狼的初始攻击力，b[i]表示第i头狼对相邻狼的加成值。
要素察觉：“被杀死的狼相邻的两头狼会变成相邻的狼”
那么就是经典的区间DP了，关键的一点在于，将一个区间表现为两个区间的和的时候如何决定先打左边区间还是先打右边的区间，如果直接比较的话好像并不准确，毕竟如果先打掉了左边区间的最右端那么又会多出一个左边区间的最右端，然后无限套娃……
既然这样，就让这两个区间无法相遇好了。
在合并区间的时候分为三个部分，左区间，中间，右区间，中间是一个大小为1的区间，这样，我在打左边区间和右边区间的时候受到的伤害都是固定的了，不过为什么我不能先打中间再打左右边呢？
所以说啊，既然在打的时候我们永远先打左边和右边再打中间，那么当中间作为“左边”或“右边”的时候不就是先打中间再打左右边的情况么，在决定带有顺序的区间dp的状态转移时千万不要陷入这种套娃的想法，我把区间分成三个部分进行转移，此时区间是按照我的转移方式进行转移的，而并不是说我根据题目区间实际的转移情况来决定状态转移，(一直想非常帅气地说一句这样的话)，复杂度为O(n3)，或许用dp优化可以使复杂度更小，但我不会。
区间dp的套路比较固定，偶尔会出现一些小的变动，让你的合并无法顺利进行，这时大部分情况只要对状态转移的方法进行一些微小调整就足够了。

那么再来一题重量级一点的：

ZOJ 3469 Food Delivery
——“区间DP的套路比较固定” ——“？？？”

可以说是绕中之绕了这一题，一开始非常难想，个人是看题解的。
为什么说这题是区间dp呢，因为外卖员不会两次经过同一个顾客，换句话讲，如果已经去过更远的位置，那么更近的位置就一定是去过的了，因此已经去过的地方是一个区间，是区间就能转移到下一个区间，而完成一个区间的时候外卖员的位置一定是在区间端点上的，因此对于每个区间，我都需要分别记录最后停留在左端点上和右端点上时的值，好，问题解决。
不过最头疼的在于，怎么转移呢，对于每个区间，用时最短的方案未必是不满意度最小的方案，因为用时的长度决定了之后的顾客不满意度的增量，但不能决定之前的，反之亦然，这就导致无后效性消失了。
……（看题解时间）
既然常规方法无法取消无后效性，那么就直接把后效也加进去好了，在状态转移的时候我直接加上在完成这段区间之后区间外的所有顾客不满意度的增量，不满意度是除了此区间外的两段区间的Bi之和，可以用前缀和来计算。
这个转移的巧妙在于将原本处于两个维度且都要考虑的时间和不满意度合成了同一个维度，当碰到无法同时处理多维度的情况时不妨想想如何把多个维度合并成同一个维度吧。
“所以说嘛，区间DP的套路就是固定啊。”