线性DP
[USACO20DEC] Sleeping Cows P
先不考虑极大，将奶牛和牛棚放在一起排序并离散化，设 \(F_{i,j}\) 为处理到第 i 个元素(奶牛/牛棚) ，有 j 头奶牛还没有进入牛棚的方案数。
对于牛棚：
\[F_{i,j}\rightarrow F_{i+1,j} \]\[j*F_{i,j}\rightarrow F_{i+1,j-1} \]对于奶牛：
\[F_{i,j}\rightarrow F_{i+1,j+1} \]考虑极大，一头奶牛可能之后会被匹配，所以我们在加入一头奶牛时就考虑它最终会不会被匹配。
注意到如果废弃了一头奶牛，那么在它之前的牛棚可以被废弃，而在它之后的牛棚不能被废弃。
如果我们去记录一头奶牛被废弃的时间，时间复杂度爆炸，但是我们发现以第一头被废弃的奶牛为分界点，后面的牛棚不能废弃，而之前的可以，所以我们只用关心当前有没有被废弃的奶牛就可以了。
新状态：
\(F_{i,j,0/1}\) 表示当前考虑了大小 \(\le i\) 的奶牛和牛棚，且有j头奶牛还未分配牛棚，目前是否钦定过不被匹配的奶牛,其中 1 表示目前没有被废弃的奶牛。
对于牛棚：
1.\(F_{i,j,1}\rightarrow F_{i+1,j,1}\quad\)废弃这个牛棚
2.\(j*F_{i,j,1}\rightarrow F_{i+1,j-1,1}\quad\)拿这个牛棚去匹配队列的一头待匹配的牛
3.\(j*F_{i,j,0}\rightarrow F_{i+1,j-1,0}\quad\)同上
对于奶牛，讨论废不废弃即可。
1.\(F_{i,j,1}\rightarrow F_{i+1,j+1,1}\)
2.\(F_{i,j,1}\rightarrow F_{i+1,j,0}\)
3.\(F_{i,j,0}\rightarrow F_{i+1,j+1,0}\)
4.\(F_{i,j,0}\rightarrow F_{i+1,j,0}\)
时间复杂度：\(O(n^2)\)
「KDOI-03」构造数组
设计状态：\(F_{i,j}\)表示目前处理到第i个，前i-1个\(a_i\)已经全部等于\(b_i\) ( \(b_i归零\) )，后面需要拿出\(j\)与前面配对，加入一个\(a_i\)，考虑还债还是继续加债，转移：
枚举拿\(u\)出来还债，其它用来加债
转移待补
\[F_{i,j}(0\le j \le \sum b_{i})*C_{u}^{l}* \]时间复杂度：\(O((\sum b_i)^2)\)
Rotating Substrings
一次操作实际上是将\(S_r\)拿出来放到\(s_{l-1}\)和\(s_l\)之间。
设计状态:
\(F_{i,j}\)表示考虑S后缀i-n，T后缀j-n，最少拿元素使后缀匹配
\(1. F_{i,j}\leftarrow F_{i+1,j+1}\quad(s_i=t_j)\)
\(2.F_{i,j}\leftarrow F_{i+1,j}+1\)
\(3.F_{i,j}\leftarrow F_{i,j+1} \; the\;number\;of\;t_j\;in\;T \le the\;number\; of\;t_j\;in\;S\)
Array Beauty
排序，设\(F_{i}\)表示美观度\(\ge i\)的方案数
答案即为\(\sum F_i\)
设计\(dp_{i,j}\)指前i个，\(a_i\)必选，序列长度为j
转移：待补
「USACO 2021.12 Platinum」Paired Up
匹配互不相交（因为相交可以交换），设计\(F_{i,j}\)表示考虑i头h奶牛和j头s奶牛
树形dp
Maximizing Root
待补
Tree Elimination
通过序列可以还原出擦边顺序，记\(F_{u,0/1/2/3}\)表示点u没擦除标记/擦除边在父边之前/擦除边为父边/擦除边在父边之后
按（u，v）的出边编号从小到大转移，形式有3种，分别为u擦除前/擦除时/擦除后
标签：7.16,奶牛,匹配,牛棚,擦除,废弃,动态,规划,rightarrow From： https://www.cnblogs.com/Linnyx/p/17557692.html