讲题入：如果同桌睡觉可以扇 ta 两巴掌。
这何尝不是 dp 呢？(指 D，乐子分讨。)
A.The Maximum Prefix
法1：
如果只求一个 k 的答案怎么做。
从后往前 dp，设 \(f_{i,j}\) 表示填了以 i 为开头的后缀，最大前缀和为 j。
转移到 \(f_{i-1,max(0,j+a[i-1])}\)。
因为我们要求最前面的前缀和一定是 0，所以每一次相当于在移动水平线。
但是这东西是倒着的，所以还是 \(O(n^3)\) 的。
设 \(dp_{i,j}\) 表示填了 i 开头的前缀，后面最大前缀为 j。
从 \(dp_{i,max(0,j+a[i])}\) 转移，贡献在开头加。
法2：
如果最大前缀和为 s，那么必然存在前缀和为 \(0,1,\dots,s\) 的位置。
对于每个 x，算 \(s\ge x\) 的概率，乘上 \(h_x-h_{x-1}\) 再求和。
枚举一个集合 p，钦定 p 中位置前缀和为 x，这个方案的权值为 \((-1)^{|p|-1}\)
\(dp_{i,j}\) 表示填了 i 个数，和为 j，对于每个 j=x，考虑是否放入，但是这东西对每个 \(x\) 都是 \(O(n^2)\)
可以对第一次到达的位置记绝对高度，其余位置记和第一个所选位的相对高度。
所以 \(h_x-h_{x-1}\) 放在第一个位置，剩下的贡献都是 -1。
B.First Come First Serve
答案显然不为 \(2^n\)，因为会出现重复。
先给定一个 x，考虑如何判定这东西是否合法。
扫描所有端点，如果序列当前数和端点编号相同，直接选掉，看能不能选完。
所以考虑加一些限制，使得选端点的情况和排列一一对应。
当 i 区间内没有选点且 i 选右端点，那么和选左端点是一样的。
容斥，显然两个不合法区间不会相交，否则必有一个合法。
一个不合法区间可以确定所有与之相交的所有区间，且这些区间编号连续，这部分可以简单预处理。
然后用一个线段树之类的东西维护就行了，每次增加一个区间 *(-1)。
c.Bow Meow Optimization
显然两个序列本身应该是单峰的，且峰在中间。
对于左半部分的狗，只跟它左边猫的数量有关，右半部也只和右半边的数量有关。
这样就相当于一个 n+m 长度的递增序列，分成两个子序列，子序列的权值就是每个位置的权值乘前面不同的数的个数。
\(dp_{i,j,k}\) 表示一个序列取了 j 个 A，k 个 B，\(O(n^3)\)。
注意力：将 A 的前 \(\frac{n}{2}\) 个放左边，B 的前 \(\frac{m}{2}\) 个放右边。
证明：
只有 01，显然成立。
对于每个 x，大于 x 的看成 1，小于的看成 0，要求对每个 x 都做最优选择。
D.Modulo Nim
全 1，全 2，后手胜。
有奇数，先手胜，\(\bmod 4\equiv 2\) 先手胜。
若 \(\bmod 3\equiv 1\) 和 \(\bmod 3\equiv 2\) 只有一个，先手胜，否则后手。
剩下只有 \(\frac{200}{12}\) 种，状压。
E.Yet Another Partiton Problem
设 \(m_j=max(A[j+1:i]})\)
在 i 右移时 \(m_j\) 是不断变化的，可以用单调栈维护。
现在有两个问题：
-
合并两段，查最优的 j。
-
对整体查关于 i 的最优解。
合并直接启发式合并就可以了，李超线段树复杂度严格，支持撤销。
但是可以发现操作序列形成树，做倍增/可撤销单调栈。
F.合唱 / Chorus
这不是原吗？但我完全不会有啥办法。
如何判一个串是不是好的，就是考虑划分子序列，看是否超过 k，每次尽量取 A，出现 B 则取 B 直到数量相同。
设 \(f_i\) 为第 i 个 B 前 A 的个数，从 \(x=1\) 开始，每次令 \(x=f_x+1\)，\(x>n\) 的跳跃次数就是子序列数。
考虑交换会改变什么，一次交换 AB 相当于在 B 前面再放一个 A，而且只改变这里。
最后的 f 需要满足 \(f_i/ge i,f_i\ge f_{i-1}\)
设 \(dp_{i,j}\) 表示跳到 i，跳了 j 次，\(O(n^3)\)
wqs 二分，可以去掉第二维。
然后剩下部分的贡献其实是关于转移到点的一次函数。
G.曲奇 / Cookies
\(\sum_{i=1}^t B_i\le \sum_{i=1}^n min(a[i],t)\)
将 B 按升序排序，\(dp_{i,j,k}\) 表示考虑 \(B_i,\dots ,B_m\)，是否可行。
可以转到 \(dp_{i,j+1,k+b_i},dp_{i-1,j,k}\)，然后还要考虑上界。
注意到 \(j\le \frac{S}{B_i}\)，状态数是 log 的，bitset 优化一下。