二分$K$

check(mid)：
能否选出$m$个点，使得 ∀i为关键点，Minjisselected{dis(i,j)}≤mid\forall i为关键点，Min_{j\ is\ selected}\{dis(i,j)\}\leq mid∀i为关键点，Minj is selected​{dis(i,j)}≤mid

进一步转化问题：
一棵树上选 $tot$ 个点，使得∀i为关键点，Minjisselected{dis(i,j)}≤mid\forall i为关键点，Min_{j\ is\ selected}\{dis(i,j)\}\leq mid∀i为关键点，Minj is selected​{dis(i,j)}≤mid，最小化 $tot$。若$tot\le m$则 check(mid) 为 true，否则 check(mid) 为 false。

定义点$i$被点$j$覆盖，当且仅当$di{s}_{i,j}\le mid$
假设当前考虑到以$x$为根的子树。
对于在$x$子树内的关键点，它们要么被$x$子树内的点覆盖，要么还等着被$x$子树外的点覆盖。
对于第二种情况，我们需要把问题留到考虑$x$的祖先时再去解决。

设$f_x$表示$x$子树内未被覆盖点到$x$的最远距离，
$g_x$表示$x$子树内被选择点到$x$的最近距离。
初值：$f_x=-\infty ,g_x=\infty$
转移：fx=max⁡{fy+1}f_x=\max \{f_y+1\}fx​=max{fy​+1}，gx=min⁡{fy+1}g_x=\min\{f_y+1\}gx​=min{fy​+1}
特判：
若$f_x+g_x\le mid$，则$x$子树内所有点都已经被覆盖，$f_x\leftarrow -\infty$
若$f_x=mid$，则$x$一定要选，$f_x\leftarrow -\infty ,g_x\leftarrow 0,tot++$
若$g_x>midandx为关键点$，把问题留给$x$的父亲解决，$f_x\leftarrow max(f_x,0)$
Code

设$f[i][j]$表示以$i$为根的子树，保留$j$个点（包括自己），删去的最小边数
初始化：$f[i][1]=son[i]$（$son[i]$表示$i$有几个儿子）
转移：f[u][j]=max{f(u,j−k)+f(v,k)−1}f[u][j]=max\{f(u,j-k)+f(v,k)-1\}f[u][j]=max{f(u,j−k)+f(v,k)−1}（−1是因为v和u之间相连的那一条边不删）

注意：我们要获得的子树的根并不一定要是整棵树的根节点
Code

基环树
如果这道题是出在树上，那就是最大独立集的裸题
设$f[i][1/0]$表示选/不选$i$ ，以$i$为根的子树的最大贡献
$f[u][1]={\sum }_{v\in so{n}_u}f[v][0]$
$f[u][0]={\sum }_{v\in so{n}_u}max(f[v][0],f[v][1])$

考虑在基环树上怎么做：
法一：强制断边
首先把环找出来
对于环上一对相邻点$(x,y)$，根据题意，$x,y$不能同时选

1. 强制$x$不选，此时$y$可选可不选，断掉边$(x,y)$无影响。断边后做树形dp，$f[x][0]$即为此情况下的答案
2. 强制$y$不选，此时$x$可选可不选，断掉边$(x,y)$无影响。断边后做树形dp，$f[y][0]$即为此情况下的答案
3. 最终答案=$max(f[x][0],f[y][0])$

Code
法二：树形dp+环形dp
博客
Code

这个题的特殊性在于儿子对于父亲节点是有影响的，
所以用$f[i][j][k]$表示第$i$号装备，其中$j$个被祖先用来合成上层装备，花费$k$元所能获得最大的力量值。

分步转移，第一步先枚举第 $i$ 号装备合成多少个，第二步再合并子树贡献。
Code

分数规划
二分答案$mid$，问题转化为：
给定一棵根为0的树。每点点权为$P_i-mid\ast S_i$，选定一个点就必须选其所有祖先节点。
问能否取$k$个节点使得取出点的点权和大于零。

设$dp[u][j]$表示以$u$为根的子树，取$j$个节点所带来的最大收益
合并就是经典树形背包
Code

基础换根dp题
$f[i][j]$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的点的权值和
$g[i][j]$ 表示 $i$ 子树外到 $i$ 距离为 $j$ 的点的权值和
Code

首先，在环中的点一定不会被遍历。
用类似拓扑排序的过程可以把环上的点全部扔掉，剩下的点会构成若干个有根树和无根树，其中有根树的根是树中唯一与环中的点相连的点。

先考虑有根树，设 $f_{i,j}$ 表示以 $i$ 为根的子树中，选 $j$ 个点的方案数
转移：$f_{i,j+k}=f{p}_{i,j}\times f_{son,k}\times \left(\genfrac{}{}{0ex}{}{j+k}{k}\right)$
特别地，$f_{i,si{z}_i}=f_{i,si{z}_i-1}$（根节点必须最后删）

对于无根树，感觉可以钦定最后一个被删的是哪个点，但更简单的方法是直接对每个点为根跑一遍有根树的算法，然后发现选 $i$ 个点的情况在没被选的 $siz-i$ 个点为根的时候会被统计，因此答案要除以 $siz-i$（如果全选是特殊情况，不需要除）

然后就是森林合并答案，就用类似合并子树的方法组合数合并就可以了
Code

换根dp
根据套路，
我们设$f_u$为修好以$u$为根的子树中的路的方案数
$g_u$为修好整棵树中除了以$u$为根的子树中的路的方案数

先考虑$f_u$怎么求：
设$f_{u,0}$表示$u$子树内无坏边的方案数，$f_{u,1}$表示$u$子树内有坏边的方案数
$f_{u,0}={\prod }_{v\in so{n}_u}{f}_{v,0},f_{u,1}={\prod }_{v\in so{n}_u}(f_{v,0}\times 2+f_{v,1})-1$
发现$f_{u,0}=1$，又考虑到$f_u=f_{u,0}+f_{u,1}$，
所以$f_u={\prod }_{v\in so{n}_u}(f_v+1)$

再考虑$g_u$：
$g_u=\frac{g_{fa}\times f_{fa}}{f_u+1}+1=g_{fa}\times {\prod }_{x\in so{n}_{fa},x\ne u}(f_x+1)+1$
因为逆元不保证存在，所以要记录前缀积和后缀积来避免除法
Code

博客

博客

博客

经典换根dp
设$f_{[}u][0]$表示 $u$子树内的点到$u$的最大/次大距离
$g_{[}u][0]$表示 $u$子树外的点到$u$的最大/次大距离

博客

博客

斯坦纳树
模板

斯坦纳树问题：

给出一个有 $n$ 个点 $m$ 条边的有权无向图，然后选定 $k$ 个点，让你求出使这 $k$ 个点联通所需的最小代价

求解：

首先，答案的子图一定是树

设 $dp[i][S]$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小代价。

转移：

对于 $i$ 的度数为 1 的情况，可以考虑枚举树上与 $i$ 相邻的点 $j$，则
$dp(j,s)+w(j,i)->dp(i,s)$
对于 $i$ 的度数大于 1 的情况，可以划分成几个子树考虑，则
$dp(i,T)+dp(i,S-T)->dp(i,S)(T\subseteq S)$

对于第1种转移，可以想到最短路模型的三角形不等式，对于每一个 $S$ ，将图做一次松弛操作即可。具体可以用 dijkstra 或 spfa 实现。
对于第2种转移，枚举子集即可。

如何优秀的枚举子集：
一个非常trivial的做法：

for(int sta=0;sta<=MAX;sta++){for(int s=0;s<=MAX;s++){if(s&sta==s){//to do sth}}
}

时间复杂度 $O(4^n)$
更优秀的实现：

for(int sta=0;sta<=MAX;sta++){for(int s=(sta-1)&sta;s;s=(s-1)&sta){//to do sth}
}

时间复杂度 ${\sum }_{sta}{2}^{||sta||}={\sum }_{i=0}^n{C}_n^i{2}^i=3^n$
Code

SOS DP+容斥

首先发现 $m$ 很小，于是直接对于每一个箱子状压
于是问题转化为选若干个数使它们按位或为全集
继续转化一下，把每个箱子取个反，问题就变成了选若干个数使它们按位与为空集

设 $g[S]$ 为有多少种选数方案使$S$为选出数的按位与的子集
答案为${\sum }_S(-1{)}^{||S||}g[S]$

设 $f[S]$ 为有多少个箱子，使$S$为其代表的数$A[i]$的子集
$g[S]=2^{f[S]}-1$

求 $f[S]$：
法一：直接枚举子集

for(int sta=0;sta<=MAX;sta++){for(int s=(sta-1)&sta;s;s=(s-1)&sta){//to do sth}
}

时间复杂度 $O(3^m)$
法二：高维前缀和解决这类子集问题

for(int i=0;i<m;i++){for(int s=0;s<(1<<m);s++){if(s&(1<<i)){f[s^(1<<i)]+=f[s];//与标准sos dp方程相比，这里的语句反过来了}}
}

时间复杂度 $O(m{2}^m)$
这种方法又称为SOS DP：博客1 博客2
Code

法一：​SOS DP
正难则反，考虑统计不合法单词数
让每个单词对应一个状态$A$，第$i$位表示第$i$个字母是否在单词中出现(1为出现)
记元音字母集的补集为$B$
则不合法单词对应的$A$均为$B$的子集
设$f[S]$表示有多少个单词，其对应的$A$为$S$的子集，可以用sos dp求出：

for(int i=0;i<m;i++){for(int s=0;s<(1<<m);s++){if(s&(1<<i)){f[s]+=f[s^(1<<i)];//标准sos dp方程}}
}

答案即为$(n-f[S]{)}^2$的异或和
Code

法二：SOS DP+容斥
设$g[S]$为元音集合为$S$时的合法单词数
设$f[s]$为有多少个单词，使$s$为其代表的$A$的子集
即$f[s]={\sum }_{i=1}^n[s\in wor{d}_i]$
$g[S]={\sum }_{s\in S}(-1{)}^{||s||+1}f[s]$
但是这样做的时间复杂度是$O(3^{24})$，会TLE，所以我们转换一下：
令$f[s]={\sum }_{i=1}^n(-1{)}^{||s||+1}[s\in wor{d}_i]$
则$g[S]={\sum }_{s\in S}f[s]$
求$f[s]$的复杂度是$O(n\cdot 2^3)$（对于每一个单词，枚举其子集）
求$g[S]$的复杂度是$O(24\cdot 2^{24})$（sos dp）
Code

法一：SOS DP+容斥
同COCI2011-2012 6
设 $g[S]$ 为有多少种选数方案使$S$为选出数的按位与的子集
答案为${\sum }_S(-1{)}^{||S||}g[S]$
设 $f[S]$ 为有多少个箱子，使$S$为其代表的数$A[i]$的子集
$g[S]=2^{f[S]}-1$
Code

法二：FWT
设$dp[i][s]$为从前$i$个数中选择，有多少种选数方案使选出数的按位与为$s$
$dp[i][j]=dp[i-1][j]+{\sum }_{k\&a[i]==j}dp[i-1][k]$
$dp[s\&a[i]]+=dp[s]$
发现这个柿子本质上就是一个和卷积，可以用FWT解决
博客

LGV引理
Code

循环了几次可以回到原地，当且仅当形成了一个环，假设每个环的长度是 $a_i$，那么$k=\mathrm{lcm}{a}_i$

又知道 $\mathrm{lcm}{a}_i$ 其实就是将所有$a_i$分解质因数，然后取每个质数的最高次幂乘起来，
所以我们可以想到枚举素数来做dp

设 $f[i][j]$ 表示前 $i$ 个素数总和为 $j$ 的所有 $K$ 的总和

枚举第 $i$ 个素数的幂进行转移：
$f[i][j]=\sum f[i-1][j-p_i^k]\times p_i^k$

可以滚动数组减掉一维
Code

双倍经验：[SCOI2009]游戏 博客

设$dp[i]$表示到了第$i$个位置的期望得分，
$f[l]$表示第$i$个位置之前有长度为$l$的连续1串的概率，
$p[i]$表示$i$为1的概率，
则有转移：
$dp[i]=dp[i-1]+p[i]{\sum }_{l}f[l]((l+1{)}^3-l^3)=dp[i-1]+p[i]{\sum }_{l}f[l](3l^2+3l+1)$

于是考虑维护
$E_l={\sum }_{l}f[l]\cdot l$
$E_{l^2}={\sum }_{l}f[l]\cdot l^2$

则总转移方程为：
$E_l[i]=p[i]{\sum }_{l}f[l](l+1)=p[i](E_l[i-1]+{\sum }_{l}f[l])=p[i](E_l[i-1]+1)$
$E_{l^2}[i]=p[i]{\sum }_{l}f[l](l^2+2l+1)=p[i](E_{l^2}[i-1]+2E_l[i-1]+1)$
$dp[i]=dp[i-1]+p[i](3E_{l^2}[i-1]+3E_l[i-1]+1)$
Code

设$f[i]$为从$i$走到$n$的期望耗时

考虑转移：
首先，我们一定不会找比当前点更劣的点转移，因为这还没有留在原地划算
其次，如果可以转移，那么转移到某点的唯一可能是比它优的点都转移不到
$f[i]=1+f[i]{\prod }_{j,f_j<f_i}(1-p_{i,j})+{\sum }_{j,f_j<f_i}f[j]p_{i,j}{\prod }_{k,p_k<p_j}(1-p_{i,k})$

$\Rightarrow f[i]=\frac{1+{\sum }_{j,f_j<f_i}f[j]p_{i,j}{\prod }_{k,p_k<p_j}(1-p_{i,k})}{1-{\prod }_{j,f_j<f_i}(1-p_{i,j})}$

实现：朴素版Dijkstra
博客
Code

设 $dp[i][j]$ 表示前 $r_i$ 分钟，把现在煎的面叫做正面，背面煎了 $j$ 分钟的最小翻面次数
显然只会在一个区间至多翻 2 次：
不翻面，$dp[i][j]=dp[i-1][j]$
翻了一次，枚举正面煎了 $k$ 秒，$dp[i][j]=min(dp[i-1][r-j-k]+1)$
翻了两次，枚举背面煎了 $k$ 秒，$dp[i][j]=min(dp[i-1][j-k]+2)$

分别用单调队列维护即可

一句话解释单调队列优化dp：如果一个人比你年轻，还比你强，那你就永远打不过他了.jpg

Code

因为对于任意一只猫，我们都可以直接算出如果有一个人要恰好接走它，需要在哪一时刻出发，我们设第i只猫对应的这个时刻为$t_i$

对于第$i$只猫，我们定义$t_i$表示如果有人在$t_i$时刻出发，此猫无须等待即可被接走
题目转化为：
现有$p$个人，要求为每个人指定一个出发时间$a_j$，最小化${\sum }_{i=1}^m(x_i-t_i)$（xi=Minaj≥ti{aj}x_i=Min_{a_j\geq t_i}\{a_j\}xi​=Minaj​≥ti​​{aj​}）

观察到每个人的出发时间$a_j$必是$t_i$中的一个
那么假设第$x$个人的出发时间是$t_i$，第$x-1$个人的出发时间是$t_j$，
则第$x$个人会接走第$j+1$到第$i$只猫
题目转化为：
现有$p$个人，要求为每个人选一只猫$b_j$，最小化${\sum }_{j=1}^p{\sum }_{i=b_{j-1}+1}^{b_j}(t_{b_j}-t_i)$

设$f[i][j]$表示考虑到第$i$个人，这个人选择了第$j$只猫的最小代价
记$s[i]={\sum }_{k=1}^i{t}_k$
则$f[i][j]$有转移式：
f[i][j]=Min{f[i−1][k]+tj(j−k)−(s[j]−s[k])}f[i][j]=Min\{f[i-1][k]+t_j(j-k)-(s[j]-s[k])\}f[i][j]=Min{f[i−1][k]+tj​(j−k)−(s[j]−s[k])}

用斜率优化求$f[i][j]$：
$f[i][j]=f[i-1][k]+t_j(j-k)-(s[j]-s[k])$
$⟺f[i-1][k]+s[k]=t_j\cdot k+f[i][j]+s[j]-t_{j}j$
把$f[i-1][k]+s[k]$看成$y$，$k$看成$x$，$t_j$看成$k$，$f[i][j]+s[j]-t_{j}j$看成$b$
现要找到一个点$P(k,f[i-1][k]+s[k])$使得$b$最小
维护一个下凸壳，并在凸包上找最优决策点$P$即可
因为$k$单增，所以可以用单调队列实现
Code

设$f_i$表示对前$i$个句子排版后的最小不协调度
记$s_i={\sum }_{j=1}^i(le{n}_j+1)$，则
fi=minj=0i−1{fj+∣si−sj−1−L∣P}f_i=min_{j=0}^{i-1}\{f_j+|s_i-s_j-1-L|^P\}fi​=minj=0i−1​{fj​+∣si​−sj​−1−L∣P}
这条转移式是有决策单调性的

感性证明：
记$h_j(x)=|x-s_j-1-L{|}^P$
不难看出$h_j$关于直线$x=s_j+1+L$对称

对于$x>s_j+1+L$的部分：
$h_j(x)=(x-s_j-1-L{)}^P$
$h_j^{\prime }(x)=P(x-s_j-1-L{)}^{P-1}$
所以$h_j^{\prime }(x)$在$(s_j+1+L,+\infty )$上单增且恒大于0

对于$x<s_j+1+L$的部分：
根据对称性，$h_j^{\prime }(x)$在$(-\infty ,s_j+1+L)$上同样单增且恒小于0

又因为函数连续，所以$h_j^{\prime }(x)$在$\mathbb{R}$上单增

又因为$h_{j_1}(x)=h_j(x+s_j-s_{j_1})$，即不同的$h_j(x)$之间可以通过平移得到，
所以$\forall j_1\ne j_2$，$h_{j_1}(x)$与$h_{j_2}(x)$最多一个交点

意会一下吧
所以 $f$ 的转移式满足决策单调性
%%%FlashHu大佬

严谨证明：
证明$w(j,i)=|s_i-s_j-1-L{|}^P$满足四边形不等式，本蒟蒻不会
贴个博客吧
Code

设$d{p}_{i,j}$表示将序列的前$i$个数划分成$j$段所需要的最小费用，
设$w_{l,r}$表示将$l$到$r$划分成一段所需要的花费
显然有转移方程：dpi,j=min{dpx,j−1+wx+1,i}dp_{i,j} =min\{dp_{x,j-1}+w_{x+1,i}\}dpi,j​=min{dpx,j−1​+wx+1,i​}

决策单调性证明：
法一（四边形不等式）：
要证$dp$的转移具有决策单调性
即证$\forall a<b,w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$
即证$\forall a<b,w(a,b)-w(a+1,b)\le w(a,b+1)-w(a+1,b+1)$
即把区间从$[a+1,b]$拓到$[a,b]$的增量$\le$把区间从$[a+1,b+1]$拓到$[a,b+1]$的增量
该式显然正确，因为在区间中增加一个元素，它对答案的贡献与区间内与它值相同的元素数量有关
法二：
记$c_x[i]$为区间$[1,i]$中值为$j$的元素个数
$h_j(i)=w(j+1,i)={\sum }_x\frac{(c_x[i]-c_x[j])(c_x[i]-c_x[j]-1)}{2}$
因为$\frac{(c_x[i]-c_x[j])(c_x[i]-c_x[j]-1)}{2}$的导函数单增，所以合起来就可以得出$h_j^{\prime }(i)$单增
结合图像可以证明$dp$的转移具有决策单调性

实现：
因为$cost(j,i)$不好快速计算，不适合用二分栈来做，所以这题是用分治实现的
Code

高中数学告诉我们：$s^2=\overline{x^2}-{\overline{x}}^2$
所以$m^2{s}^2=m\sum v_i^2-(\sum v_i{)}^2$
$-(\sum v_i{)}^2$为定值，我们只要令$\sum v_i^2$最小即可
设$f[i][j]$表示把前$i$段路分为$j$天走，${\sum }_{k=1}^j{v}_k^2$的最小值
记$s_i$表示前$i$段路的长度和
则$f[i][j]$有转移式：f[i][j]=min{f[x][j−1]+(si−sx)2}f[i][j]=min\{f[x][j-1]+(s_i-s_x)^2\}f[i][j]=min{f[x][j−1]+(si​−sx​)2}

斜率优化：
$f[i][j]=f[x][j-1]+(s_i-s_x{)}^2$
$⟺2s_i{s}_x+f[i][j]-s_i^2=f[x][j-1]+s_x^2$
把$2s_i$看成$k$，$s_x$看成$x$，$f[i][j]-s_i^2$看成$b$，$f[x][j-1]+s_x^2$看成$y$
找最优决策点即找到点$(s_x,f[x][j-1]+s_x^2)$使得$b$最小
Code

容易得到递推式：$f[n]=f[n-1]\times 10^{len(n)}+n\mathrm{mod}m$
构造转移矩阵：
$$\left[\begin{array}{ccc}f[n]& n& 1\end{array}\right]=\left[\begin{array}{ccc}f[n-1]& n-1& 1\end{array}\right]\times \left[\begin{array}{ccc}10^{len(n)}& 0& 0\\ 1& 1& 0\\ 1& 1& 1\end{array}\right]$$
如果不是$10^{len(n)}$这个奇怪的变量，这道题已经做完了
那我们干脆把$10^{len(n)}$变成常量：枚举位数，对每一个位数做一次矩阵快速幂

经典结论：
用矩阵$A$表示有向图$G$的连通情况（$A_{i,j}=1$表示$G$中存在边$i\to j$）
那么从$s$到$t$经过$k$条边的路径数=$(A^k{)}_{s,t}$

拓展到本题：
我们定义一种新运算$\ast$：
$$\left[\begin{array}{cccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,m}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,m}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n,1}& a_{n,2}& \cdots & a_{n,m}\end{array}\right]\ast \left[\begin{array}{cccc}{b}_{1,1}& b_{1,2}& \cdots & b_{1,n}\\ b_{2,1}& b_{2,2}& \cdots & b_{2,n}\\ ⋮& ⋮& \ddots & ⋮\\ b_{m,1}& b_{m,2}& \cdots & b_{m,n}\end{array}\right]=\left[\begin{array}{cccc}{c}_{1,1}& c_{1,2}& \cdots & c_{1,n}\\ c_{2,1}& c_{2,2}& \cdots & c_{2,n}\\ ⋮& ⋮& \ddots & ⋮\\ c_{n,1}& c_{n,2}& \cdots & c_{n,n}\end{array}\right]$$
其中ci,j=Mink=1m{ai,k+bk,j}c_{i,j}=Min_{k=1}^m{}\{a_{i,k}+b_{k,j}\}ci,j​=Mink=1m​{ai,k​+bk,j​}
因为$\ast$运算满足结合律，所以$A\ast A\ast A\ast \cdots \ast A$仍然可以用快速幂求得

在这种新运算下，如果初始矩阵中$A_{i,j}$表示$i$到$j$的最小距离
那么从$s$到$t$经过$k$条边的最短路径长度=$(A^k{)}_{s,t}$（这里的$A^k$表示$k$个$A$相$\ast$）
博客

首先本题需要确定一个事实：
每一次的拔高操作区间右端点一定是最右边的玉米

设$f[i][j]$表示以 $i$ 结尾，$i$ 这个点已经被 $j$ 个拔高区间覆盖过，所能得到的最长不下降序列长度
f[i][j]=max{f[k][l]}+1(1≤ｋ<i,0≤l≤j,h[i]+j≥h[l][k]f[i][j]=max\{f[k][l]\}+1(1\leqｋ<i,0\leq l\leq j,h[i]+j\geq h[l][k]f[i][j]=max{f[k][l]}+1(1≤ｋ<i,0≤l≤j,h[i]+j≥h[l][k]

用数据结构优化转移即可
Code

博客
Code