晚上有答辩模拟赛，显然翘掉???。
上午下午无聊的很啊，于是学了一些杂项，比如啥 prufer、kruskal 之类的，反正考前这段时间也是摆了??，倒不如好好珍惜?。
考完 noip 会有多少人退役啊???。北校目前不知道，南校这边 haosen 看我和 l6t 退不退，我看 haosen 和 l6t 退不退?，现在我们俩都是 l6t 的支配点了???。而且感觉我们这个机房大概率会退一大半人，哎。没办法，都是迫于生活。要不是回班会受苑苑的气，同时还留恋着在机房颓废的时光，估计也早就回班了吧。
当然具体退不退役也得看 NOIP 考成什么狗屎了???。
先不说 NOIP 考成什么狗屎?，就这傻逼模拟赛也就成狗屎了???。我草这 vjudge 上的模拟赛真就一坨屎，真他妈不知道选题人脑子萎缩了还是纯粹没脑子，死吗玩意的选个这破屎模拟赛。NOIP 模拟赛就模拟了个题目数量是吧?，题目都他妈不是 OI 题你他妈的叫啥呢?，真就放点 ACM 的题就能当 OI 模拟赛了是吧?。
选题人真他妈就一纯纯的废物，死妈的玩意。
而且这什么傻逼翻译我草：“则输出“DISLIKE”（不带引号，下同）（这意味着你不能用字母代替问号，这样熊猫夫⼈就喜欢这⾸歌）”。要么就是机翻要么就是翻译的人大脑萎缩???。
guess not.
傻逼模拟赛我他妈有考这吊玩意的时间去他妈 vp 两场 CF 都比这强??。我也很能理解 S2 最近这么几年我只见到过 zzz 这么一个 Au 了?。S2OI 就算似了我也觉得正常，好似?。
放点乐图：
晚上 P 了一张苑苑，也是怕吓到大家就不放了。
明天上午还有模拟赛，希望正常一些，你搞个信心赛我都没疑问?，别搞成一坨答辩就行?。毕竟没人喜欢别的傻逼把答辩喂给你还强迫让你吃?。
板子留到 11.19 再打???，闲话先更到明天，后天就写游记了???。
推歌：Crimson Throne -Dimier√Lisb
应该是这个名字来着?。arcaea 给依莉丝觉醒的角色曲，敲起来真的很爽?。
但是我没买这首/qd，我买的是 manic jeer?。
和我名字也比较搭呢???。
AGC017F
首先显然的做法是状压线的左右走向，然后每次枚举上一条线以及这一条线的走法，复杂度为 \(O(4^n\mathrm{poly}(n,m))\)。
可以考虑进行一个轮廓线 dp，每次仅转移折线走的一步。具体的，我们设 \(f_{i, j, s, d}\) 为转移了前 \(i\) 条折线，当前这条折线转移了前 \(j\) 层，目前折线的走法为 \(s\) 的前 \(j\) 位，上一次的走法为 \(s\) 的后 \(n-j\) 位，当前与上一次的折线相差距离为 \(d\)，转移显然，复杂度 \(O(n^2m2^n)\)。
考虑优化状态，其实根本没有必要记录 \(d\) 这一维，而可以选择在转移的过程中动态维护分界线。可以规定一个假想的分界线，当前这条折线的所有走法都是贴合这条折线的。为了维护这条分界线，可以进行一个分类讨论。
-
分界线向右
此时只需要向右走，无需改变分界线形状。
-
分界线向左且当前选择向左走
同上。
-
分界线向左且当前选择向右走
这时需要画图来直观理解。
图中黑色细线为原本的分界线，此时向右转移，分界线变为红色。设向右走为 \(1\)，向左走为 \(0\)，那么新分界线的状态即为去掉当前状态后 \(n-j\) 位中最低位的 \(1\)。于是就可以进行转移。
对于 \(k\) 条限制的处理是简单的，不再赘述。
时间复杂度 \(O(nm2^n)\)。
这题其实暑假集训的时候讲了（，前几天把这题补完也算是无憾了吧，毕竟一直想写这道题来着。
