其实这题很容易设出四维的 $\rm{DP}$ ，也就是用 $dp_{i,j,x,y}$ 表示第一个序列的终止位置为 $i$ 且长度为 $x$，第二个序列的终止位置为 $j$ 且长度为 $y$ 是否成立 ，然后也很容易想到降维，枚举当前序列长度 $len$ 的时候知道了 $x$ 就已经知道 $y$ 了—— $y$ 就是 $len-x$ 。也就是说现在的 $DP$ 是 $O(n^3)$ 的，还需要优化。

$loj$ 上没有此题，$bzoj$ 上是权限题，对于不上 $yzoj$ 的我来说只能去洛谷做题了：转送门😄 。

我们先不考虑边的权值(<与>)，这样子 $n-1$ 条边组成的就是树了，很显然是需要我们求出这棵树的合法拓扑序的个数，考虑使用 $\rm{DP}$ ，对于边的方向(即<,>) ，我们分类讨论即可。

首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数，但是这个时候如何计算呢

有趣的题目，可爱的传送门：戳这呢=￣ω￣=

刚开始往概率 $\rm{DP}$ 想了，发现对于一个点的概率是好算，但是如果求贡献的话就会很难办。最后万般无赖的点开了题解，发现居然是……组合数学？其实和 $\rm{DP}$ 没有半毛钱关系。

我们考虑一个节点 $i$ ，我们枚举其子树大小 $j$ 。现在考虑最终有多少种合法的情况可以使得 $i$ 的子树大小恰好为 $j$ 。

概率神仙题的传送门：别戳偏了

设 $f_i$ 表示还剩下 $i$ 盏灯亮到还剩下 $i-1$ 盏灯亮的期望操作次数，这个时候有 $\frac{i}{n}$ 的概率按中亮的，但是没有按中亮的的话就只能退到 $f_{i+1}$ 。不难列出转移方程：

因为转移式中有个 $f_i$ ，有些不好办……推一推式子康康。

以后不要被这种傻逼题给蒙骗了。传送门：方伯伯的传送门=。=

首先要明确一个道理，每一次拔高的右端点一定是 $n$ ，如果是只拔高中间部分，右边的又要尽可能大于中间部分，索性一起拔了，这一定是最优的。

设 $f_{i,j}$ 表示第 $i$ 个玉米被拔高了 $j$ 次时以 $i$ 结尾的最长不下降子序列长度，容易得出转移方程：

传送门在这：我是传送门$QwQ$

其实不难发现，我们需要算的就是 $\sum a_i$ (其中 $a_i$ 为点 $i$ 的通电概率) 。我们需要算出每个点的通电概率即可。因为有些点可以自己发电，所以我们要分别考虑父亲和儿子的通电情况。

因为直接设通电概率有些棘手，我们设 $f_i$ 表示点 $i$ 的儿子没有向点 $i$ 通电的概率，这个比较好算，我们顺带算上点 $i$ 自己发电的概率。

首先，两个数不互质同理于两个数的质因子集合没有交集。考虑一下 $n\leq 30$ 的情况，可以发现这里面的质数也只有 $10$ 个，那么我们将每一个寿司分解质因数，然后将质因子压成一个状态。

设 $f[s1][s2]$ 表示小 $\rm{G}$ 吃了的寿司的状态为 $s1$ ，小 $\rm{W}$ 吃了的寿司的状态为 $s2$ 时的方案数。转移的时候枚举寿司，分别判断两个人是否能吃然后转移即可。

其实这道题是 $\rm{POI}$ 的原题，$loj$ 传送门链接：在这呢o(￣︶￣)o

刚开始肯定还是看不出这题是什么 $\rm{DP}$ ，感觉很诡异，但是推一推自然就出来了：

设 $f_i$ 表示 $i$ 的 $p$ 值，那么继续：

可爱的题目传送门：戳我戳我·(╹▽╹)·

说实话这道题如果单看斜率优化 $\texttt{DP}$ ，但是如果没猜到那么多结论，你是怎么也想不到”斜率优化”是从哪里来的。那么我们开始猜结论吧……

• 1. 初始水位小于 $h_1$ 的没有用。

这很显然。