呃这个可能会用作讲稿?
呃现在确定要用作讲稿了，寒假里会给小朋友讲。作为弱校选手，公开的资源很重要，自己写的东西肯定是会给大家公开的/se
打算继续公开校模拟赛题，因为反正所有题都是搬的（
sdfz还没牛逼到有人可以出模拟赛。上古时期的模拟赛题，有两个合集可以在Czzsy0531(讲道理，应该是cunzai_zsy0531)的luogu blog找到。
来更新第二部分，也就是dp转移结构。
刚才我们好像也说过，扫描线方向和dp转移结构有交，但是没有一个包含另一个。
在扫描线方向之外的转移结构实在是没有多少种，并且往往是计数dp里面的一些东西。下面用两道例题说明两种常见的。
AGC002F Leftmost Ball
有$n$种颜色的球，每种有$k$个。把这些球全都排成一排，每一种颜色最左边的那个涂成白色，求有多少种不同的最终颜色序列。$n,k\leq 2000$，答案膜$10^9+7$。
如果没有染白大家都会算!
如果有染白，一种最终的序列就可以对应多种排列了。如何去重?
先考虑两个排列什么时候会算重。如果它们除了最后被染白的部分都相同，只有染白了的部分做了某些交换，那就会算重交换的方案次。注意到这个方案是难以计算的，所以这条路走不通。
考虑判定什么样的序列是可以搞出来的。容易发现这是一个类似括号匹配的过程，它要求每个颜色的球第一次出现的时候，前面都有充足的白球作为这个颜色失去的真正的第一次出现。
那么我们给每种颜色第一次出现赋权值\(-1\)，白球赋权值\(1\)，问题变成所有的前缀和都为正。容易想到一个dp，设\(dp(i,j,k)\)表示填了\(i\)个位置，已经有\(j\)个颜色出现了一次……你发现转移需要记这些颜色分别还剩多少球，因为题目要求每种颜色恰好\(k-1\)个。这个也行不通了。
换个决策顺序，我们每次往序列里填一个颜色的所有\(k-1\)个球。设\(dp(i,j)\)表示已经填了\(i\)个白球和\(j\)个别的颜色的球的方案数，那么每次可以选择 :
- 填一个白球，这会使得……草?你发现这需要记一车东西，所以我们并不能这么决策。考虑一些别的决策方法。
考虑左边第一个空位放什么。如果放白球，那么啥事没有；如果放别的颜色的球，我们就组合数选出剩下的位置即可。有\(dp(i,j)=dp(i-1,j)+\binom{nk-i-(j-1)(k-1)-1}{j-2}dp(i,j-1)\)。
loj2743 joi open 2016 C. 摩天大楼
给一个序列，求有多少种重排(数值相同的两个数，初始位置不同，也是相区分的)，使得相邻两项差的绝对值之和\(\leq k\)。\(n,a_i,k\leq 1000\)。
复杂度像是\(n^2v\)或者\(n^3+v^2\)之类的。
扫序列毫无前途，我们扫值域。考虑最大的那个数，它的贡献一定是正的。
考虑次大的数，它的贡献几乎是正的，除非它和最大的挨着，那么它会贡献一次负的。第三大的数，如果挨着最大的和次大中的两个，那么会贡献两次负的，挨着一个则贡献一次负的，不挨着则都贡献正的。
我们怎么描述 和更大的数挨着 这种事情呢?我们可以在旁边两个位置上留一手接头，表示放在这两个位置会贡献一次负的，如果一个位置被标记两次那就是贡献两次负的。不妨把它们称作1接头和2接头。
考虑我们怎么才能记录两类接头的数量。你发现不能，因为位置会影响数量的变化。遇到了僵局。
不要考虑数量的变化，我们钦点这些接头!也就是说放进一个数去，直接钦点它左边和右边的接头在被消除的时候是1还是2，如果是2那就需要留一手，让后面一个数来把它变成2，留一手这类接头我们称为1.5。接下来我们记录有多少个1/1.5/2接头即可。然而还是有问题，我们如果要把左右两个1都变成2，可能实际上没有位置可以做这件事，这就很难受。
这个思路完全失败了。还有什么?
可以考虑插入而不是摆放。这两个都是常见的转移结构。
此时扫值域的优势完全体现了出来，我们插入一个数，两边的数都比它大，设这三个数分别是\(a,x,b\)，那么贡献会增加\(2(\min(a,b)-x)\)。考虑我们把这个拆开，每次插入之后直接把\(2(\min(a,x)+\min(x,b))=4x\)扔进总和，\(-2x\)在插入的时候加进去，这样。同时维护所有空位多加了的东西，也就是所有间隔的\(\min(a,b)\)之和，最后减去即可。
你发现这个多加了的东西没法维护，因为我们插入的时候，需要知道这个间隔原来的\(\min(a,b)\)，这就完蛋了。
怎么才能把这个去掉?考虑我们在插入的时候，钦点新产生的空位以后还会不会被插入，也就是多记一个还有多少没被钦点没了的空位，转移的时候我们只往这种空位里面放，最后所有的空位都被钦点了，那就对了。
设\(dp(i,j,0/1/2,k)\)表示考虑前\(i\)个数，有\(j\)个中间的空位没被钦点，\(0/1/2\)个边上的空位没被钦点，当前总和是\(k\)。转移就是考虑插到中间还是边上，然后新产生的空位是否要钦点。写一发你发现对了，OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO!但是这个的状态数是\(O(n^3v)\)，转移是\(O(1)\)，过不了。
考虑对第三维优化掉一个\(n\)，我们需要某种方法使得统计和的时候不会有负的，这样就可以利用\(L\leq 1000\)了。考虑我们这个东西实际上是一个线头dp，我们留接头的时候，可以一边扫一边加上这一步的长度乘上线头的个数，而不是进行差分。这就做完了。如果要直观描述这一做法的话，就是把这个排列想象成折线，然后从上往下扫，记录扫描线上方的长度和接头的个数。