这题真的是。。不想说了，刚开始不敢加第三维，然后看题解发现第一维可以压掉。。
然后如果我们设$f[i,j,k]$为$A$匹配到$i$, $B$匹配到$j$, 已经分了$k$个部分的方案总数，在转移的时候发现不能判断某一个字符取了还是没取，那么加一维, $f[i, j, k, 0]$表示不取，$f[i, j, k, 0]$表示取。
那么分别转移：
$$f[i,j,k,0]=f[i-1,j,k,1]+f[i-1,j,k,0]$$
$$f[i,j,k,1] = f[i-1,j-1,k,1] + f[i-1,j-1,k-1,1] + f[i-1,j-1,k-1,0]$$
在$A[i]==B[j]$时，才能更新$f[i,j,k,1]$
初始化时$f[i,1,1,0] = s​$, $s​$为前$i​$个字符能匹配$B[1]​$多少次，那么每次枚举，都$f[i,1,1,0]=s​$, 如果当前为能够匹配，则$f[i,1,1,1] = 1，s+=1​$
最后答案是$f[n,m,k,0]+f[n,m,k,1]$
注意本题要取模，并且要计算空间复杂度不然会爆炸

题目是一个无限背包+01背包，但是要先做无限背包，再做01背包。如果先做01背包，那么在做无限背包的时候会出现多次下降的情况。
根据题目，很容易想出设$f[i][j]$为在$x=i, h=j$时的最小点击次数，那么有下列方程(无限背包部分, 即上升部分)
$$f[i][j] = min(f[i][j], f[i-1][j-kx]+1)$$
很明显，这样的做法TLE。
我们回想无限背包的式子，$f[v] = max(f[v], f[v-w[i]]+c[i])$对吧？应该大部分人都记得这个“滚动后的式子”，而原式都不记得了，原式为设$f[i][v]$为前$i$个物品装进$v$容量的最大利益。则状态转移方程为
$$f[i][v] = max(f[i-1][v], f[i][v-w[i]]+c[i])$$
这个方程是”继承$f[i-1]$的值“或者”在$f[i]$中已经计算过的值再用来转移(即实现了多重)”，我们的原方程是不是也可以这样呢？答案是肯定的。
原方程可化为
$$f[i][j] = min(f[i][j-x]+1, f[i][j-x]+1)$$
这样就不会超时了，处理之后的01背包，直接在多重处理完后扫一遍，$f[i][j] = min(f[i][j], f[i-1][j+y])$就能算出来了。
注意此题要因为上升高度大于$m$则为$m$，需要进行特殊判定，并且每个是管道的状态也要转移，因为这个对多重做出了贡献，在处理完之后再进行覆盖最大值即可，否则这里会丢掉25分。直接沦为暴力选手

BZOJ 3400
Luogu 2947
from: USACO 2009 Mar Sliver(USACO刷题第19题)

维护一个从顶到底单调递减的单调栈然后就可以求解了。

BZOJ 1614
Luogu 1948
from: USACO 2008 Jan Sliver(USACO刷题第18题)

如果去掉一条路径上的边，肯定要优先删掉大的边，所以我们可以二分整条路径上的第$k+1$大的边，把比他小边的设为0，大的设为1
然后最后的$dis[n]$就是如果第$k+1$大的边为当前二分$mid$值，所需要免费的边数，即可判断可行性。
注意：无向图的边数组要开多两倍！！！牢记！！！

BZOJ 1610
Luogu 2665
from: USACO 2008 Feb Sliver(USACO刷题第17题)

刚开始想到搜索每个点然后求斜率…然后并不行
看题解以后直接全部求出来排序去重就可以了…

求斜率公式：$$k = \frac{y_1-y_2}{x_1-x_2}$$
推导过程：设两个点为$(x_1, y_1),(x_2, y_2)$，它们之间连线的解析式为$y=kx+b$
将两点坐标带入解析式，得$y_1=kx_1+b, y_2=kx_2+b$
$y_1- y_2$，得$ y_1-y_2=kx_1-kx_2$
$k(x_1-x_2) = y_1-y_2$
即$k = \frac{y_1-y_2}{x_1-x_2}$

注意，比较两个浮点数的大小为$fabs(a-b)<eps$即相等, $eps$为最小误差值

BZOJ 1612
Luogu 2419
from: USACO 2008 Jan Sliver(USACO刷题第16题)

根据题目的胜负关系可以想到要建图建图，然后关键是怎么才能判断出某个点是否可以确定名次
如果一个点和它连通的点的个数为$n-1$，那么这个点一定可以确定名次，正确性显然
数据小，用Floyd传递闭包判连通即可求一个点和它连通的点的个数

BZOJ 1641
Luogu 2888
from: USACO 2007 Nov Sliver(USACO刷题第15题)

最大值最小，第一反应二分。
但是这题把样例化画出来以后发现可以用最短路跑，改一下松弛为
$$G[i][j] = min(G[i][j], max(G[i][k], G[k][j]))$$
数据小Floyd水过。
注意邻接矩阵重边问题！

BZOJ 1638
Luogu 2883
from: USACO 2007 Mar Sliver(USACO刷题第14题)

一开始只能想到暴力做法，看了题解才知道怎么做
首先，对于一条边$(a,b)$, 设入度为0的节点为$w$, $path(x, y)$为$x -> y$的路径条数
根据乘法原理，经过该边次数为
$$path(w, a) * path(b, n)$$
这样我们可以分别求出$path(w, a), path(b, n)$，$path(w, a)$即$g$使用反图$RG$用DP求解，$path(b, n)$即$f$使用原图$G$用DP求解

BZOJ 1633
Luogu 2875
from: USACO 2007 Jan Sliver(USACO刷题第13题)

刚开始根本没想到DP，什么kmp，AC自动机，后缀数组都想了。。看了题解才知道
解决字符串的几大武器：(字符串DP，字符串Hash，KMP，AC自动机，后缀家族……)

本题设$f[i]$为给定串前$i$个字符进行处理后最少删除的字符数。
刚开始想了个超时的方法。。然后发现其实直接写就行了。。还是太弱
方程：$$f[i] = min(f[i], f[k]+cnt)$$
其中$k$满足$[k,i]$之间能够被字典中的词匹配(可以删字符)，$cnt$为为此删除的字符数
初始化$f[i] = i$

BZOJ 1635
Luogu 2879
from: USACO 2007 Jan Sliver(USACO刷题第12题)

之前看完题目想到差分约束，然后是个区间不知道怎么搞。。看完题解是差分序列。。
差分序列和差分约束并不是毫无关系啊。。差分约束运用于两个元素，差分序列运用于区间。。

本题对于每个约束$a,b$，如果$a>b$，显然，交换不会影响结果
我们设$f[i]$为差分序列，然后对于每个约束$a,b$，我们使$f[a+1]–, f[b]++$，这样可以保证$a,b$之间的元素严格小于$a,b$
之后前缀和加上最高高度即可。前缀和一定不会大于$0$，因为每次操作都是在左边$-1$，右边$+1$
本题可能会有重复的约束，要排序以后去重(考试的时候一定要注意这种问题)