动态规划的状态设计 | bot 讲课の补题

sto james1badcreeper orz.

好厉害的题，但是怎么有人补了三天才补完呢？

CF1810G The Maximum Prefix

线性 dp，怎么有 bot 说题目难度在 *2400~*2800 之间结果开场就是 *3200 啊 /youl

尝试直接正着做，发现要记 fi,j,kfi,j,k 表示前 ii 个数，最大前缀和是 j，当前前缀和是 k 的答案。然后发现哪一维都压不掉。
所以要换状态，设 fi,j 表示考虑了前 i 个数，[i+1,n] 贡献的最大前缀和是 j 的期望得分。初值为 f0,i=hi。转移有

fi,j←fi−1,j+1×pi+fi−1,max(0,j−1)×(1−pi)

长度为 n 的答案显然是 fn,0，长度为 k 的答案等价于 k 后面对答案没有贡献，为 fk,0。

---

P3188 [HNOI2007] 梦幻岛宝珠

调了 inf 年，死于数组越界。顺路拍挂了篇题解。
发现 b 只有 30 种，先根据 b 的值分组，对每组分别背包。然后考虑怎么合并。
设 fi,j 表示只考虑 b∈[0,i]，已经选的体积在 W 二进制下的后 i−1 位符合条件，仍额外多出来 j×2i 的体积。
枚举 b=i 的物品选了 k 个，设 W 第 i−1 位是 Wi−1，转移是

gi,j=jmaxk=0{gi−1,2(j−k)+Wi−1+fi,k}

---

UVA10559 方块消除 Blocks

一年前贺题解的题，现在还是不会！
首先本来就颜色一样的连续一段不会拆开选，我们可以把它当成一个点，并记原长度为 len。那么处理后的序列相邻两点颜色不同。
设 fl,r 表示消完 [l,r] 完全没法做，改为设 fl,r,k 表示区间 [l,r]，r 将要和后面 k 个颜色一样的点合并。
那么如果 r 只和后面的消不和区间内其他的消，有 fl,r,k←fl,r−1,0+(lenj+k)2。
否则在区间里先消掉一段使 r 和区间里某个数并在一起，枚举 x 满足 colx=colr，有 fl,r,k←fl,x,k+lenr+fx+1,r−1,0。
时间复杂度 O(n4)，但因为一开始的合并操作减小了 n，基本跑不满。

---

P7605 [THUPC2021] 小 E 爱消除

17:40 开始做，22:15 调过了，令人感动。说实话真挺好奇场上过了几个人(

把这两个东西放在一起转移。设 gl,r 表示管子里只剩 [l,r] 的球，最少剩的球数 / 最小的杯子大小。

对于当前区间，如果考虑从两端取出数和外面的栈合并，发现栈是没法用 dp 维护的。我们只能使用向内考虑配对的思路。换句话说我们只考虑 [l,r] 区间本身的结果，不考虑原来栈里已有的东西。

这里以先从左边取为例，如果这个球最后也没有被消掉，从 gl+1,r 转移。
否则枚举跟 l 配对的球 i，满足 coli=coll。那么想让他们匹配，我们要做的事情是先取 l，再消掉 i 左边或右边的所有数，取出 i。

分类讨论 i 最后从哪边被取出。

• 从左取出，那么 [l+1,i−1] 这段区间要全消掉。如果它不能自己消干净，也可以用 [j,r] 来辅助。枚举 j，则答案为 将 [l+1,i−1] 和 [j,r] 一起消除的答案 和 gi+1,j−1 取 max。

设 fa,b,c,d 表示把 [a,b] 和 [c,d] 一起恰好完全消除需要最小的杯子大小。

• 从右取出，那么 [i+1,r] 这段要全消掉。同样枚举 j，答案从 fl+1,j,i+1,r 和 gj+1,i−1 转移。

先取右边同理。

再转移 f。
同样地，分类讨论先取 a 还是先取 d，再讨论与它配对的在哪段区间，从左边还是右边取。

发现如果 f 里面有任意一种颜色出现了奇数次，一定是消不掉的，可以在记搜里直接剪枝，用异或的性质判断(类似 P1469)。
同时因为转移限制了很多同色，有效的状态数很少，官方题解说常数大概是 1720。

---

P3748 [六省联考 2017] 摧毁“树状图”

精神污染题。啥时候没事干了再写。

---

P4099 [HEOI2013] SAO

写了一年树形背包终于知道树形背包怎么写了。
设 fu 表示只考虑子树 u 的拓扑序数量，结果发现可以先删 v 子树里的一堆东西再删 u 再删 v，因此状态要多记一维。fu,i 表示只考虑子树 u，点 u 在拓扑序中第 i 个的方案数。
枚举子树 v 内在 u 之前删的数量 j 和点 v 在自己子树的排名 k。边从 u 连向 v 就钦定 k>j，否则 k≤j。
那么转移方程是

fu,i+j←fu,i×fv,j×(i+j−1j)×(sizu−i+sizv−jsizu−i)

k 那一维直接前缀和优化掉，就是标准的树形背包复杂度。
发现同一个 v 下的 f 不能转移到自己(j 有 0)，开个辅助数组区分一下。

---

[ABC025D] 25個の整数

看数据范围 25 个格子 20 个空位，确定是状压。
考虑从小到大填数的过程，设 fi 表示点集 i 中的位置已经被填过了数，其余位置还没有填。因为我们钦定了从小往大填，状态 i 下最后一个填的数就是 i 中 1 的个数。
那么填这个数的限制条件就是它不会在横向或竖向上形成单调数列。
以横向为例，填在位置 x 不合法当且仅当 x 左右恰好已经有一个位置被填了。因为已经被填那个位置肯定比当前数小，没被填那个位置最后填的东西一定比当前数大。
转移的时候判断一下合法性，时间复杂度为 O(n2n)，取决于实现方式 n 取 20 或 25。

---

[CF1585F] Non-equal Neighbours

CF1585F & 1591F，两个一样的题但一边题解全是线段树，另外一边全是容斥，好离谱。

直接 dp 是 O(nV) 的，考虑容斥。钦定有 i 对相邻数相同，发现这个东西要考虑好几对数连成一段的情况，还是不好求。
但上面的问题给我们一个启发，有 i 对数相同等价于把序列拆成不多于 n−i 段。
那设 fi,j 表示前 i 个数分成 j 段，有朴素 dp：

fi,j=i−1∑k=0fk,j−1×min{ak+1,…,ai}

最后统计答案就是

ans=n∑j=1(−1)j+nfn,j

状态还要优化，发现我们只关心 j 的奇偶性而不关心具体是什么。设 fi,j 表示前 i 个，钦定分成奇数还是偶数段的方案数。方程改成

fi,j=i−1∑k=0fk,j⊕1×min{ak+1,…,ai}

再优化转移复杂度，考虑后面 min 的值。设第一个比 ai 小的位置在 lsti。那么小于 lsti 的 k 可以直接从 flsti,j 转移过来。
求 lst 用单调栈。那么式子是

fi,j=flsti,j+i−1∑k=lstifk,j⊕1×ai

把 ai 拆出去，∑fk,j⊕1 用前缀和优化，时间复杂度 O(n)。

---

[ARC061D] 3人でカードゲーム

把所有取出的牌写成序列，充要条件是出现 n 个 a 的时候，b,c 的个数不超过 m,k 个。
我分别枚举的 b,c 填几个，推了一车式子。貌似直接枚举 b,c 的总数 s 更简单，可以直接组合意义(bot 您这里少写了一项系数啊 QAQ。

ans=m+k∑s=03m+k−s(s+n−1n−1)m∑i=s−k(si)

后面一半没法快速算，考虑利用组合数的递推性质。

f(s)=m∑i=s−k(si)=m∑i=s−k(s−1i−1)+(s−1i)=f(s−1)−(s−1k)+f(s−1)−(s−1m)

可以根据上式预处理 f。

---

[CF1750F] Majority

正着不会做，反过来找序列不合法的条件：

• 两端不都是 1
• 操作到最后，存在某段连续 0 的长度大于两边 1 的长度之和

设 fi,j 表示长度为 i 的串，钦定开头结尾都是 1，操作到不能操作，结尾连续 1 的个数。
那么 fi,i 是合法情况，由不合法的情况容斥得到：fi,i=2i−2−2j<i∑j=1fi,j。
求不合法的 fi,j，那么序列的最后一段在全部操作后一定是一段连续的 0 后接一段连续的 1。枚举 0 的长度为 k，1 的长度为 l。
转移有

fi,j=fj,j×(∑j+k<i∑j+l<kfi−j−k,l)=fj,j×∑(i−j−k)+l<i−2jfi−j−k,l

使用前缀和优化，设 sk=∑i+j≤kfi,j。转移变为 O(1)，时间复杂度 O(n2)。

---

P5128 好时光

简单题。
先把 n 转成 k 进制，题意就是求 k 进制下所有小于 n 的数最长的等差区间的长度之和，考虑数位 dp。

首先常规地记录 pos 表示当前 dp 到第几位，limit 表示是否要卡上界。
然后记录我们要求的答案(最长等差长度)为 mx，以当前位为结尾的等差数列长为 len。
为了判断是不是等差，我们要知道上一位和公差是什么。公差有负数不好塞进状态，改为记录前面两位的值分别是 fi,se。

转移的时候枚举这一位填 i，有

fpos,len,fi,se,mx,limit→fpos−1,len+1,se,i,max(mx,len+1),limit & i=apos(i=se+(se−fi))

fpos,len,fi,se,mx,limit→fpos−1,2,se,i,mx,limit & i=apos(i≠se+(se−fi))

吐槽一下卡空间和这个神秘模数，记忆化的时候只记录 limit=0 的部分，不然会 MLE。

---

P4719 【模板】"动态 DP"

上个月学过，等哪天没事干再复习一下。

---

[TJOI2018] 游园会

lyn 学长居然讲过这种东西 /xia 原来只有 yxcat 啥科技都不会。

dp 套 dp 板子。
观察到“不能有子串 NOI”的限制是容易处理的，所以我们先忽略这个限制，只 dp LCS 的长度。
一开始的想法是设 fi,j,len 表示前 i 个，在兑奖串上匹配到 j，LCS 的长度是 len。当然完全是错的。
因为 LCS 不能贪心匹配，你需要知道前 i−1 个的 LCS 是什么。这个东西难以直接塞进状态里。
考虑 LCS 的原 dp 过程：

fi,j=max(fi−1,j,fi,j−1)

fi,j=max(fi,j,fi−1,j−1+1)(si=tj)

我们把长度为 k 的序列 fi 塞进 i 的 dp 状态里，上面的转移就可以实施了。但是 fi 序列状态数太多，而且直接状压有很多不合法。
考虑将 fi 差分，那么每位只能是 0/1。这样状态数就只有 2k，可以压进外层 dp 的状态里。fi,j,k 表示前 i 个，LCS 的 dp 数组答案为 j，与 "NOI" 的匹配长度是 k 的方案，转移的时候暴力 dp 一遍 j，找到新的状态。

---

[CEOI2016] kangaroo

第一次见这个经典(？)trick。没见过确实想不到 /oh
考虑从小往大加数，这一点和前面那个 abc 题差不多。但是这里我们维护已经被填数的位置形成了多少个连续段。
设 fi,j 表示插入了前 i 个数，形成了 j 个连续段的方案数。
考虑现在填 i，题目的限制等价于 i 要么左右都没填，要么左右都填了。也就是说两种情况：

• i 左右都没填，新增了一个连续段。fi,j←fi−1,j−1×j；
• i 左右都填了，合并了两个连续段。fi,j←fi−1,j+1×j。

起点终点的限制问题随便判一下就好了。

---

[AT DP string] 文字列

感觉考点不是 dp 是组合数。
设 fi,j 表示前 i 个，有 j 对相邻(这里要明确“对”的概念，比如 aaa 是 2 对相邻)。
考虑字符 i，枚举它新加进来的时候有 a 对相邻，拆开了原来的 b 对。求得放完之后有 j+a−b 对相邻。
那么在 j 对中选 b 个拆开、在 cnti 个字符中选 a 对相邻、在剩下的 sumi−1+1−j 个空位中放啥也没干的 cnti−a−b 个字符。

fi,j−b+a=cnti−1∑a=0j∑b=0(jb)(cnti−1a)(sumi−1+1−jcnti−a−b)fi−1,j

---

[JOISC2019] ふたつの料理 (Two Dishes)

这题好厉害。
设 fi,j 表示 A 做到第 i 步，B 做到第 j 步的最大分数。把这个东西放在坐标系上考虑，即每次可以向上或向右，走一条从 (0,0) 到 (n,m) 的路径。
再考虑把限制也丢到坐标系上，A 的限制是一条左上到右下的折线，这条线在路径左上方的部分贡献进答案。B 的折线在路径右下方的贡献进答案。
发现有两个方向不好搞，我们考虑对 A 容斥，先把 p 全加进答案里，再减右下方的贡献。
然后发现 dp 方程长成了这样：

f(x,y)=max(f(x,y−1),f(x−1,y)+y∑i=1v(x−1,i))

把 x 那维当成时间轴，我们要维护的就是 n 次操作，每次对一个后缀区间加 w，然后让整个区间每个数取前缀 max。
考虑维护差分序列，w>0 就直接加，否则往后找第一个作为 max 的位置，把中间的差分数组都清零即可。
这个东西用 map 维护，复杂度可以均摊：每次修改至多增加一个不为 0 的位置，w<0 的情况最多一共向后跳 n 次。

---

什么？摧毁树状图？不会有人想补这玩意吧。

完结，但越写题越发现自己怎么这么菜，所以不想撒花。