CSP 2019 集训 贪心和动态规划

贪心

简单贪心

排队接水

用邻项交换的方法可以证明，是从时间短到时间长排序。

区间选取

每次尽量选早结束的区间。

选点覆盖区间

每一个区间用尽量靠右的点覆盖。

删数字

从最高位开始，如果后一个数字比前一个数字小，那么就删去这个数，删够 $k$ 个为止。

数位乘积

注意到如果把末尾的一些数字改成 $9$，乘积可能会变大。

枚举要把末尾的多少位数字改成 $9$，求 $\max$ 即可。

进阶贪心

均分纸牌

像网络流一样，每个点最后的净流入/出是一定的，而且端点的流入/出只有一个方向。因此只需要进行那一次净流入/出就可以了。

环形均分纸牌

Usaco 2012 Mar Haybale Restacking

设 $1$ 与 $n$ 的流量为 $x$，就变成一堆绝对值之和的函数了。

合并果子

参照哈夫曼树。

ONTAK 2010 Creative Accounting

BZOJ 3544.

给定数列 $A$ 和一个模数 $p$，找一段区间，使得区间和模 $p$ 最大。

使用前缀和转化，对每一个 $S_r$，都找一个 $S_l(1\le l<r)$，使得 $S_r-S_l$ 模 $p$ 最大。

分成两段，用 set 维护就可以了。

反悔型贪心专题

概述

使用贪心算法的一个条件是“局部最优可得出整体最优”，但是很多时候，这是不成立的。

但有些情况下，我们可以通过“反悔”操作，修改局部最优解的一个或几个操作，使得局部最优解导出全局最优解。

EXPEDI - Expedition

拿到题目，如果我们不敢用贪心怎么办呢？

如果是 dp，那么状态数实在是爆炸啊。

所以在考虑 dp 状态优化的时候，我们想到了贪心。

有一种贪心策略是，只加油最多的加油站。但是这样的问题是，可能在到达好的加油站之前，车子已经没油了。

考虑“子问题”。设“子问题”是走到第 $i$ 个加油站，油箱容量一直非负的情况下，最少的加油次数。

下面要从第 $i$ 个加油站走到第 $i+1$ 个加油站，要是车子目前油足够还好说，直接更新油量即可；若是油不够呢？

我们先前已经对“每个加油站加不加油”作出了决策，现在发现油不够了，是要反悔了没有？

怎么反悔？“唉，要是我们在之前那个加油站加过油就好了。”可以在之前没有加过油的、油量最多的加油站加一次油。由于我们是迫不得已才加油，因此加油次数是最少的。

把经过的加油站的油量放进堆里，每次取堆顶即可。

数据备份

同样是一道反悔的贪心。由于相邻两个数不能同时取，因此我们设置一个“自动反悔”的机制，即若 $a,b,c$ 相邻，选了 $b$ 后把三者删除，加入 $a+c-b$。今后如果选了 $a+c-b$，就意味着反悔了。这样就能平衡局部最优与全局最优的矛盾。

Cow Coupons

先考虑简单的情况：如果钱很少，没买完优惠的牛就花完了呢？那当然是直接贪心取优惠价最低的若干头牛，也就是取 $C_i$ 最小的一段。

那么如果把 $k$ 张优惠券用完了，还剩有钱呢？

这时候就有牛需要按原价购买了。我们原先选的牛价格低，但是优惠幅度不一定大，在钱比较多的情况下买它们不一定划算。

怎么办呢？我们考虑反悔，也就是调换优惠券的使用对象，原先买的牛不用优惠券，现在买的新牛使用优惠券。于是代价就是 $C_j+(P_i-C_i)$。

还可以从另外的角度考虑这个问题。为什么 $C_i$ 前 $k$ 小的牛一定要买呢？不妨假设某头 $C_i$ 前 $k$ 小的牛 $\alpha$ 没有买，那么一定有一头 $C_i$ 较大（不是前 $k$ 小）的牛 $\beta$ 使用了优惠券；把牛 $\beta$ 调换成牛 $\alpha$，答案不会变劣。

因此 $C_i$ 前 $k$ 小的牛是一定要买的，但是不一定使用优惠券，因为可能有其他的牛优惠幅度更大。因此上述反悔型贪心的算法是正确的。

综上，反悔型贪心可以着重考虑“局部最优解”如何转化为“全局最优解”，通过转化使得贪心算法变得正确。

动态规划

递推与动态规划

斐波那契, LIS。

动态规划的使用条件

最优子结构

整个问题的最优解蕴含子问题最优解。

无后效性

下一时刻的状态仅与当前状态有关，与前面的状态无关。如果不满足就要扩充状态才行。

动态规划的一般做题方法

1. 设计状态
2. 设计转移，注意转移方向
3. 注意初值
4. 计算复杂度

动态规划的分类

1. 线型动规
2. 背包问题
3. 区间动规
4. 树形动规
5. 状态压缩动规
6. 记忆化搜索
7. 特定的动态规划优化方法：决策单调性、斜率优化

线型动规

LIS, LCS (子段/子序列)

背包问题

01 背包、多重背包、完全背包、分数背包。

其实还有有依赖的背包、分组背包等。

区间动规

石子合并

设 $f[i][j]$ 表示区间 $[i,j]$ 全部合并的最小代价，枚举分割点（最后一次合并的位置）。

环形石子合并

环形问题要么考虑断环成链，要么倍长环。

这题可以考虑倍长环，在得到的链中取所有 $n$ 长区间的最小答案即可。

能量项链

据说只是把 $+$ 变成了 $\times$。

[CQOI 2007] 涂色

设 $f[i][j]$ 表示区间 $[i,j]$ 都被涂好的最小代价。

每个区间肯定不会被涂超过一次，而且涂的区间“重叠而不覆盖”没有意义。（“重叠而不覆盖”指的是两个区间交集非空但不是子集关系。）

下面把所有涂色方案分类。考虑涂的过程中有没有涂 $[i,j]$ 这个区间。

如果没有涂这个区间，那么一定可以找到一个点 $k$，使得不存在一次涂色，同时涂了 $k$ 和 $k+1$。这个是由“不存在重叠而不覆盖的两个区间”性质保证的。于是我们枚举断点 $k$，令 $f[i][j]=\min(f[i][j],f[i][k]+f[k+1][j])$。

如果涂了这个区间，那么一定是因为这个区间的头和尾是一样的，我们想要先涂满这个区间，再在其上覆盖。因此这种情况仅当 $a[i]=a[j]$ 时才会发生。

如果我们强制不能涂这个区间呢？那么头和尾都必须单独着色，着色次数会多 $1$，且情况转换为“没有涂这个区间”。于是像上一种情况那样转移。

但是，实际上我们是涂了 $[i,j]$ 这个区间的，因此实际上着色次数要减 $1$，转移完成后减 $1$ 即可。

综上，$f[i][j]=\min(f[i][k]+f[k+1][j])-(a[i]==a[j])$。程序实现很简单，但是想出情况的转化还是有难度的。

树形动规

没有上司的舞会

由于每个点选不选对它的父亲有影响，因此要记录到状态中。

骑士

刚才那道题的基环树版本。

对于环，我们可以断环成链，也可以倍长环。由于环上的点外面还挂有东西，因此不方便倍长环。于是可以选择断环成链。

如何断环成链呢？我们找到环上的某一条边，把它断开，再人工考虑断开边的影响——我们强制边上的某一个点不可选。

强制当然可以直接特判，但这里有一个比较神奇的方法。直接把禁用的点的权值设为 $0$ 即可！（当然如果不放心，可以设为 $-\infty$）。

POI 2008 STA

这道题才是换根 dp 的模板吧。

换根的影响非常简单，子树内的点深度减 $1$，子树外的点深度加 $1$。

USACO 2008 Jan 手机网络

树上最小支配集。

每个点可能被自己、父亲或孩子控制，需要分别讨论一下。

类似的题目有“消防局的设立”，不过那个控制的范围更广一些。

DAG 动规

HAOI 2016 食物链

裸题。

状压动规

疾病管理

$f[i][j]$ 表示前 $i$ 头牛，疾病集合为 $j$，直接转移即可。

另外还有更简单的贪心做法：枚举最终的疾病集合（所含疾病个数不超过 $k$），对每一个集合，扫描所有牛，统计有多少牛的疾病是当前集合的子集。

混乱的奶牛

记录最后一头奶牛和当前已选的奶牛。

送外卖

由于是环，因此一个环会被算 $n$ 次，非常不划算。我们强制环从 $1$ 开始，这样就只需要记录当前环上点的集合和最后的点即可。

互不侵犯

按行选择，记录当前选了几行、放了几个国王、当前行的状态即可。

概率动规

SGU495 Kids and Prizes

概率论解法：考虑每一个盒子，它没有被任何人选到的概率自然是 $(1-\frac{1}{n})^m$，于是可以计算出它被选的概率，也就是它被选的期望。把所有盒子的期望加起来（其实就是乘以 $n$，或者说是独立观察量）就得到答案了。

概率 dp 解法 1：设状态是 $i$ 人，选了 $j$ 个礼物的概率。进行一些变换可以得到更好的递推式。

概率 dp 解法 2：设状态是第 $i$ 个人得到礼物的概率。如果上一个人没有得到礼物，那么这个人得到礼物的概率和上一个人一样；如果上一个人得到了礼物，那么这个人得到礼物的概率少了 $\frac{1}{n}$。同样化简可以变得更好。

记忆化搜索

可以简化实现，甚至可以剪枝。

经典动规算法

Floyd

$f[i][j][k]$ 表示允许经过点 $[1,k]$ 中转的前提下 $i,j$ 的最短路，$f[i][j][k]=\min(f[i][k][k-1]+f[k][j][k-1],f[i][j][k-1])$。第三维度滚动压掉。

理解这个意义很重要，有专门考这个的题。

动态规划的优化

琪露诺

很明显的单调队列优化。

LIS

有两种数据结构的优化方法。

一种是反转值域后用单调数组，比较巧妙。

另一种是令 $f[a[i]]$ 表示以 $a[i]$ 结尾的 LIS 的长度，然后利用动态开点线段树或离散化+树状数组就可以了。

动态规划的 NOIP 例题

加分二叉树

因为有了序列，所以不是树形 dp，是区间 dp。

注意考虑边界情况。

合唱队形

把 LIS 和 LDS 合并起来就行了。

过河

离散化后单调队列（？）。

金明的预算方案

由于附件很少，因此直接枚举附件的选取情况。

如果附件比较多，先对每一棵树做一次背包，然后分组背包即可。

传纸条

由于两个路径不能相交，而相交的两个点到起点的路径长度一定相同，因此只要保证两条路径在距离起点相等的地方不相交即可。

这样我们对两条路径同步走，$f[i][j][k][l](i+j=k+l)$ 表示两条路径分别到达 $(i,j),(k,l)$ 的方案数。另外由于 $i+j=k+l$，因此可以压掉一维 $l$。

乌龟棋

由于当前位置和用过的四种卡片的数量是线性相关的，因此可以压掉当前位置。

花匠

考场上估计会写 $O(n\log n)$ 的树状数组/线段树/set 优化 dp。

当然这题还有一个更巧妙的方法，结合贪心，直接考虑与上一个的联系，如果这一个比上一个小，那么要么把上一个作为峰、这一个作为谷，要么不选这一个——因为上一个作为峰肯定比这一个作为峰更好。经过一番神奇 dp，就可以 $O(n)$ 得到答案。另外还有直接贪心构造解的办法。

动态规划的高级应用

最大半连通子图 (Part)

裸题？别忘了只是一个部分分。

如果使用记忆化搜索，就不需要拓扑排序了。

Treats for the Cows

因为是双端队列，所以就只能 dp 了，而且是区间 dp。

另外这题实际上可以按区间长度滚动数组。

Round Subset

有二维属性的背包？

值域上不可能有两个数，因此可以把其中一个数拿到定义域里。$f[i][j][k]$ 表示前 $i$ 个数、选了 $j$ 个、其中有 $k$ 个 $5$ 因子时 $2$ 因子的最多个数。

计算量有点大，但毕竟是 CF 评测机嘛，信仰过。

New Year Santa Network

又是树上点对 / 点组的问题，确实不能考虑以点组作为计数主体，一定会 TLE 的。因此我们考虑计算边的贡献。

我们发现，树上三个点之间的三对距离经过一条边要么是 $0$ 次，要么是 $2$ 次——如果三个点分布在这条边的两侧（一边 $1$ 个、一边 $2$ 个），那么贡献是 $2$ 次；否则贡献是 $0$ 次。

贡献为 $2$ 次的情况数当然是 $\mathrm{C}^2_p\times \mathrm{C}^1_q+\mathrm{C}^1_p\times \mathrm{C}^2_q$。

修改边的时候用贡献乘以 $\Delta w$ 即可。

树上染色

如果我们两两考虑点对，那肯定是要超时的。

如果我们考虑树边对答案的贡献如何呢？一条树边对答案的贡献应该是“子树内外黑点数量之积”加上“子树内外白点数量之积”再乘以边权。接下来做一个树上背包就可以了。

关于复杂度，有一个参考证明。

Outer Space Invaders

拿到这道题，好像没有什么思路？每个外星人都有出现时间和消失时间，贪心似乎不太能做……

我们先把外星人抽象成区间 $[a_i,b_i]$，画在高度 $d_i$ 上——也就是一条从 $(a_i,d_i)$ 到 $(b_i,d_i)$ 的线段。

每次操作就是选取一个点 $(x_i,y_i)$，表示在 $x_i$ 时间进行一次半径为 $y_i$ 的攻击，这次攻击可以消灭所有在时刻 $x_i$ 存在的、半径不大于 $y_i$ 的外星人，也就是消除所有与线段 $(x_i,0),(x_i,y_i)$ 相交的线段。

似乎还是没有什么思路？这里有一种“极限思考法”——没有思路的时候，考虑“最 xx”这样的特殊的元素。我们考虑半径最大的外星人，我们肯定需要一次半径为 $y_i$ 的攻击来消灭它，但是在什么时刻攻击还不确定；并且，这一次攻击能够消灭此时存在的一切外星人。

也就是，如果我们按照半径从大到小考虑所有外星人，那么我们就不需要收到“半径”的限制，已消灭的外星人就是若干个连续的区间——可以区间 dp！

虽说是“区间”，但是我们还是没有搞清楚呐……

想一想记忆化搜索吧。

假设我们枚举“最强外星人”在时刻 $t$ 被消灭，那么还剩下哪些外星人需要被消灭呢？当然是还剩“时刻 $t$ 之前消失的外星人”和“时刻 $t$ 之后出现的外星人”了。于是子问题就变成了“消灭时刻 $t$ 之前消失的外星人”和“消灭时刻 $t$ 之后出现的外星人”。

假设“在时刻 $t$ 之前消失的外星人”中，我们枚举“最强外星人”在时刻 $t'$ 被消灭。那么剩下的外星人当然是“在时刻 $t$ 之前消失的外星人”和“在时刻 $t’$ 之后出现、但在时刻 $t$ 之前消失的外星人”。

终于找到规律了吗？我们的子问题其实是“在时刻 $l$ 之后出现、但在时刻 $r$ 之前消失的外星人”，原问题是“在时刻 $0$ 之后出现、但在时刻 $n+1$ 之前消失的外星人”。

于是这个区间 dp 终于定义完全了！转移方程也随之而来——$f[i][j]=f[i][k-1]+f[k+1][j]+g[k]$，其中 $g[k]$ 表示在时刻 $k$ 存在的所有外星人的半径的最大值。这个转移表示“在时刻 $k$ 进行一次消灭在场所有外星人”的操作，其合理性已在上面论述。

因此，很多时候记忆化搜索可以作为思考的切入点（“脚手架”），当然也可以作为实现的方式。

Problem a

这些信息很多，怎么整理成容易处理的形式呢？

我们要为每一个人安排一个准确的分数吗？好像非常困难啊。

再思考一下每一个人说的话是什么意思。“有 $a_i$ 个人比我分数高，有 $b_i$ 个人比我分数低”其实对“比我分数高”的人和“比我分数低”的人这两部分都没有要求，叙述的只是“把所有分数排序后， $(a_i,n-b_i]$ 这一个区间是一个极大连续相等的段，并且我是其中的一个元素”。

我们把每一个人说话的区间整合起来，把区间相同的人进行合并。如果同一个区间 $(a_i,n-b_i]$ 的人数超过了 $n-a_i-b_i$，那么多出的人一定在说假话。接下来就是处理数轴上不同的区间了。

如果两个不同的区间相交，就会出现矛盾，这是因为相等是等价关系，具有传递性，不同的极长连续相等区间是不可能相交的。因此问题变成了在数轴上选若干个不相交的区间，使得它们的权值和最大。

把每一个区间的左右端点记为 $L_i,R_i$，按 $L_i$ 排序依次处理，$f[i]$ 表示前 $i$ 个区间（必选第 $i$ 个）的最大权值和，那么 $f[i]=\max(f[j])+w[i]\ (R_j<L_i)$。

这个东西可以用线段树或者树状数组优化到 $O(n\log n)$，于是问题解决。

这题告诉我们要如何抽象处理信息。

庆典

求把正整数 $n$ 写成 $m$ 个不同正整数的和的方案数，$n\le 10^5$。

“不同正整数”启示我们可以把整数从小到大排序，接着如果使用差分数组就可以很好地描述这个数列的性质——差分数组的每一项都为正。

差分数组中第 $i$ 位的数对答案的贡献是 $(m-i+1)d_i$，按照这个 dp，设状态 $f[i][j]$ 是前 $i$ 个数、对和的贡献为 $j$ 的方案数，那么 $f[i][j]\rightarrow f[i+1][j+(m-i)d_{i+1}]$ ，其中 $d_{i+1}$ 是所枚举的差分数组第 $i+1$ 位的值。

状态总数是 $O(nm)$ 的，转移好像又不止 $O(1)$……感觉不太行的样子。不过可以用记忆化搜索 + 强剪枝搞掉不可能状态，也许有一定希望。

但是！转移其实是可以 $O(1)$ 的。

这其实就是一个完全背包——每一个位置上的数的体积分别是 $m,m-1,\cdots,m-i+1,\cdots,1$，都有无穷多个，求把背包装满的方案数是多少。实际做的时候，我们不需要枚举 $d_{i+1}$，只要像完全背包一样顺序枚举 $j$，并从本行转移（$f[i+1][j]\rightarrow f[i+1][j+(m-i)]$，并滚动数组）即可！因此，熟悉经典的背包模型，对解题还是很有帮助的。差分数组也是处理单调递增 / 递减问题的好方法。

注：上述方法有缺漏。这个和完全背包有区别，因为完全背包某个物品可以不选，但是这里不能不选。因此需要对完全背包的方程进行一些改动，变成 $f[i][j]=f[i-1][j-(m-i+1)]+f[i][j-(m-i+1)]$。

这里又提供两种方法。

一种方法是，先把差分数组的每一个数设为 $1$，计算这些 $1$ 的总贡献。剩余的贡献要给差分数组里的某些数一点点加 $1$，给每个位置的数作调整对答案的贡献都不一样。接下来就考虑“给前 $i$ 个位置加了 $1$，总贡献是 $j$”即可。

另一种方法是，构造一个每一个数都不相同的集合，可以有两种操作：给集合中所有数加 $1$、给集合中所有数加 $1$ 后再加入一个 $1$——也可以从差分数组的角度理解。

注：这里有一个可以提交的类似的题目：51nod 1201 整数拆分，但是这道题没有限定拆成多少个数。

这样怎么办呢？没有确定的 $m$，我们又应该如何计算差分数组每个数的贡献呢？

这里有一种办法：把差分数组倒过来，每个位置存储“这个位置的数比下一个数大多少”，那么第 $i$ 个位置的数对和的贡献就是 $i$ 了。于是就可以对所有的 $m$ 都进行计算了。

集合选数

这是一个有向无环图上独立集的计数问题，我们可以先把图画一画。

在纸上稍微画一画就会发现，这是一个网格图森林！这是因为，$2x$ 的三倍和 $3x$ 的二倍都是 $6x$。而且网格图的宽不会很大，只有 $\log_{3}n\approx 10$。

于是就可以在网格图上按列做状压 dp，最后把不同的网格图的答案乘起来就可以了。

这道题的关键还是发现图的性质。

Eden 的新背包问题

有 $n$ 个物品，每个物品有若干个。有 $Q$ 次询问，每次询问用 $V_i$ 的背包能装下的物品的最大价值，但是要求不能用物品 $D_i$（每次询问给定一对 $V_i,D_i$）。

$n,V_i\le 1000,\ Q\le 1000$ 怎么做？那当然是做一个前后缀背包然后简单合并一下就好了。

如果 $Q\le 3\times 10^5$ 怎么办？这时候就不能每次查询都合并了！

我们考虑离线之后进行 CDQ 分治或者线段树分治。（怎么想到的？区间太多大概是需要分治的吧(bushi)。联系分治 FFT。）

Hotel

求树上三元点集 $\{u,v,w\}$ 的数量，要求三个点两两等距。$n\le 5000$。

考虑三个点的中间点（必定有这样一个点），它到三个点等距。把这个点作为根，变成了计算来自三个不同子树、深度相等的点的个数。

这个应该不是很难进行树形 dp。

Osu! Easy

这题比 osu! 一些图的 Easy 难多了……

我们需要详细定义随机变量，这样有利于理解。注意，下面的几段都还没有引入期望。

随机变量的推导可以认为是涵盖了各种可能情况时的推导。再次提醒，这里还没有期望！

$L_i$ 表示以第 $i$ 个点击结尾的 combo 的长度。对于 x，$L_i=0$；对于 o，$L_i=L_{i-1}+1$，也就是不论 $L_{i-1}$ 如何，$L_i$ 总是等于 $L_{i-1}+1$。对于 ?，情况比较复杂，$L_i$ 有 $\frac{1}{2}$ 的概率等于 $L_{i-1}+1$，有 $\frac{1}{2}$ 的概率等于 $0$。

$F_i$ 表示假如在第 $i$ 次点击后游戏意外退出（这个说法好牵强），此时的得分（或者可以理解为进行到第 $i$ 次点击时游戏界面显示的分数，打过 osu! 也大概知道吧(大雾)）。

考虑如何从 $F_{i-1}$ 计算 $F_i$ 呢？这当然是考虑第 $i$ 次点击对分数有多少贡献啦。假如第 $i$ 次点击 miss 了，那么 $F_i$ 当然等于 $F_{i-1}$。但是如果成功了，那么 combo 加长了 $1$，分数增加了多少呢？

由于 $(x+1)^2=x^2+2x+1$，也就是 $(x+1)^2-x^2=2x+1$，于是 combo 增长 $1$ 对答案的增加量应该是 $2L_{i-1}+1$。

因此，对于 x，$F_i=F_{i-1}$；对于 o，$F_i=F_{i-1}+2L_{i-1}+1$；对于 ?，上述两个等式成立的概率各为 $\frac{1}{2}$。

或者，我们可以定义随机变量 $\Delta_i=F_i-F_{i-1}$。对于 x，$\Delta_i=0$；对于 o，$\Delta_i=2L_{i-1}+1$；对于 ?，上述两个等式成立的概率各为 $\frac{1}{2}$。

这些可都是随机变量的分布啊，我要它干什么呢？

算期望确实要用到概率，接下来我们开始了！

由于期望的线性性，$\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1}+\Delta_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(\Delta_i)$。因此，我们只需要想办法计算出 $\mathrm{Ex}(\Delta_i)$，就可以很容易地递推出 $\mathrm{Ex}(F_i)$ 了（其实就是 $\mathrm{Ex}(\Delta_i)$ 的前缀和嘛）。

对于 x，由于 $\Delta_i$ 恒等于 $0$，因此 $\mathrm{Ex}(\Delta_i)=0$。

对于 o，由于 $\Delta_i$ 恒等于 $2L_i-1$，由期望的线性性，$\mathrm{Ex}(\Delta_i)=\mathrm{Ex}(2L_{i-1}+1)=2\mathrm{Ex}(L_{i-1})+1$。

对于 ?，我们要根据分布列计算 $\mathrm{Ex}(\Delta_i)$，也就是把两种情况下的取值与概率相乘，加权相加——这应该算是全期望公式的应用吧。由于 $\Delta_i$ 取上述两种式子的概率各为 $\frac{1}{2}$，因此 $\mathrm{Ex}(\Delta_i)=\frac{1}{2}(0+2\mathrm{Ex}(L_{i-1})+1)=\mathrm{Ex}(L_{i-1})+\frac{1}{2}$。

上面的三个式子中有两个出现了 $\mathrm{Ex}(L_{i-1})$，因此我们在计算 $\mathrm{Ex}(\Delta_i)$ 的同时也要计算 $\mathrm{Ex}(L_i)$。

对于 x，由于 $L_i$ 恒等于 $0$，因此 $\mathrm{Ex}(L_i)=0$。

对于 o，由于 $L_i$ 恒等于 $L_{i-1}+1$，由期望的线性性，$\mathrm{Ex}(L_i)=\mathrm{Ex}(L_{i-1}+1)=\mathrm{Ex}(L_{i-1})+1$。

对于 ?，我们还是要根据分布列计算 $\mathrm{Ex}(L_i)$。由于 $L_i$ 取上述两种式子的概率各为 $\frac{1}{2}$，因此 $\mathrm{Ex}(L_i)=\frac{1}{2}(0+\mathrm{Ex}(L_{i-1})+1)=\frac{1}{2}\mathrm{Ex}(L_{i-1})+\frac{1}{2}$。

这样我们所需的所有递推式都全了，可以整理如下：

\begin{cases}\begin{align} &\mathrm{Ex}(L_i)=0,&a_i=\mathrm{x} \\ &\mathrm{Ex}(L_i)=\mathrm{Ex}(L_{i-1})+1,&a_i=\mathrm{o}\\ &\mathrm{Ex}(L_i)=\frac{1}{2}\mathrm{Ex}(L_{i-1})+\frac{1}{2}, &a_i=\mathrm{?} \end{align}\end{cases}

\begin{cases}\begin{align} &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1}),&a_i=\mathrm{x} \\ &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+2\mathrm{Ex}(L_{i-1})+1,&a_i=\mathrm{o}\\ &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(L_{i-1})+\frac{1}{2}, &a_i=\mathrm{?} \end{align}\end{cases}

初始值是 $F_0=L_0=0$。我们已经把辅助变量 $\Delta_i$ 处理掉了。

注意一个要点！$F_i$ 的式子里不要出现 $L_i$，因为这样在应用全期望公式的时候会出问题。简单地说，就是全期望公式里面已经在讨论这个 ? 是否 miss 的这两种可能性了，但是 $\mathrm{Ex}(L_i)$ 里面同样包含了这个 ? 是否 miss 的讨论，一个事件重复讨论就会导致问题；或者说，在全期望公式里，已经假设（或者说在……的条件下）了这个 ? 是否 miss，因此应该代入的是已经确定下来的上一个状态，而不是代入目前这个状态。如果不好理解，可以试着把 $\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(L_i)-\frac{1}{2},\ a_i=\mathrm{?}$ 代入 ? 这个序列计算，就会发现问题。

所以这道题就不用数组解决了。话说这题二次方是道蓝题，还有一道三次方的是一道紫题，真是不可理喻(bushi。

Vasya and Binary String

此题略（大雾）。

POI2004 PRZ

不是特别困难的状压 dp。

BZOJ3791 作业

首先我们可以把连续的语文作业或数学作业累积在一起，这样序列就变成严格语数交错的了。

下面有一个结论：$k$ 次操作可以生成所有不超过 $2k+1$ 块的序列。所谓“块”是指极长的连续 $0$ 或 $1$。

可以用数学归纳法证明，要点是“在一段 $1$ 中间选一个区间变为 $0$，会变成 $101$，一次操作可以多产生 $2$ 个区间”。

于是就可以 dp 了。$f[i][j][d]$ 表示第 $j$ 段的末尾是 $i$，变成了 $d\ (d\in\{0,1\})$ 序列时的最大收益，考虑上一段在哪里就可以了。

百度之星 最强密码

给出一个只含小写字母的字符串 $A$，求最短的只含小写字母的字符串 $B$，使得 $B$ 不是 $A$ 的子序列（子序列可以不连续）。求 $B$ 的长度和方案数。$\vert A \vert\le 10^5$。

我们怎么判断一个序列是不是另一个的子序列呢？先在 $A$ 中找 $B_1$ 第一次出现的位置 $i_1$，在 $i_1$ 之后找 $B_2$ 第一次出现的位置 $i_2$，在 $i_2$ 之后再找 $B_3$ 第一次出现的位置 $i_3$……

因此“$B_j$ 匹配到 $A_i$”的 $i$ 和 $j$ 是重要的状态。设 $f[i]$ 表示匹配到 $A_i$ 的最小的 $j$，那么我们枚举 $B_j$ 的下一个字符 $c$，找到 $A_i$ 之后第一个为 $c$ 的字符 $i'$（找不到则为 $n+1$），更新 $f[i']=\min(f[i'],f[i]+1)$，同时统计方案数即可。

找 $i'$ 的过程可以用一个数组维护，这样转移变为 $O(26)$。

The Minima Game

每个人都会从大到小取数，进行 min-max dp 即可。

Treasure Chest

状态不难想，但是卡空间怎么办呢？

dp 压空间，当然是用滚动数组啦。如果按长度顺序转移，那么 $l$ 只会由 $l-1$ 转移到，所以只记录左端点就可以描述状态了。

花仙子的魔法

这题的 dp……很难理解吧。

实在不行就找规律 + 大力拉格朗日吧。

严格 $n$ 元树

不错的题目。

如果设状态为“深度为 $i$ 的严格 $n$ 元树的数量”，那么子节点的深度怎么限制呢？可以有至多 $n-1$ 个儿子深度小于 $i-1$，但是必须有一个儿子深度为 $i-1$……难道要用容斥？

似乎容斥也是可以的——$f[i]=(f[0]+f[1]+\cdots+f[i-1])^n-(f[0]+f[1]+\cdots+f[i-2])^n$，初始条件 $f[0]=f[1]=1$。

当然这里有更巧妙的办法。设 $g[i]$ 表示深度不超过 $i$ 的严格 $n$ 元树数量，那么 $g[i]=1+g[i-1]^n$——怎么理解呢？考虑严格 $n$ 元树的深度，可以是 $0$（这时只有 $1$ 种），可以大于 $0$（这时根节点的每一棵子树都是深度不超过 $i-1$ 的严格 $n$ 元树）。

因此，很多时候放松限制条件也是 dp 状态设计的一种方法。