乱记随机做到的dptricks
交换状态与答案
适用场景：状态大但是答案小
- AT_dp_e Knapsack 2
- CF176D Hyper String
- AT_agc033_d [AGC033D] Complexity
用map存
写出明显存不了的状态的柿子之后 发现只有比较少的几个会有更新，那就用map存
维护两个最优值->一般把值域较小的那个放到状态里
两个最优值指在一个最优的情况下保证另一个最优
- P1773 符文之语
关于区间dp
一种是合并类型的，状态二维，时间复杂度\(O(n^3)\)
一种是分割类型的，状态一维，时间复杂度\(O(n^2)\)，对于这种来说，转移时后半段是完全固定的，如果再加一维只需要一重循环枚举整段（填表）/分割的前一段（刷表）
- P1773 符文之语
又出现了一种，大区间不是由两个小区间合并而来，而是一个，应该用在一些对两头进行操作的东西。
- P3607 [USACO17JAN] Subsequence Reversal P 选择子序列反转转化成头尾对调，然后一直这样扩展到某一步继续对调。因为要构成不降子序列，能否由一个较小的扩展到较大的只和其最值与两端新加入的大小关系有关，所以再开两维记最值。要注意初值应当做到哪些状态，比如这个题区间长度是1的不管值域如何全要覆盖到。别忘了最值是不严格的，这种东西不要忘了从[mn+1,mx]和[mn,mx-1]转移。code
改变转移顺序
一个状态可以由多个状态转移而来（这几种转移方式等价），可能可以尝试通过改变转移顺序达到缩减状态某几维值域的作用，从而优化dp
- Equal Sums
神仙题，设\(f_{i,j,s}\)表示做到i与j，数组之和差值为s的方案数，将一行行转移改成刷表，若\(s>0\)则转移j，否则转移i，这样就能将s值域控制在\([-w,w]\)中。另外，填表的前缀和优化相当于刷表的差分优化。code
根据不等关系缩减状态
一些对转移有很多限制的题，可以通过解不等式缩小某些状态维度的范围/减少维度。
- P6647 [CCC 2019] Tourism 一开始设的状态是\(f_{i,j}\)为前\(i\)分为\(j\)天的方案数，总天数为\(\lceil \frac{n}{k} \rceil\)。
首先显然有\(j\geq \lceil \frac{n}{k} \rceil\)
若\(j> \lceil \frac{n}{k} \rceil,j+ \lceil \frac{n-i}{k} \rceil > \lceil \frac{n}{k} \rceil + \lceil \frac{n-i}{k} \rceil \geq \lceil \frac{n}{k} \rceil\)，不优。
因此\(j= \lceil \frac{n}{i} \rceil\)。
状态缩减为\(f_i\)表示划分到\(i\)后的最大贡献，转移每隔\(k\)个分段（前一天）。
拆分max(或者别的可合并的东西)
对于一些端点关于两个变量的\(\max\)转移，可以拆分开来分别关于一个变量，通过预处理之类的优化转移。
- P6647 [CCC 2019] Tourism
令\(q\)为上一段的右端点
\(f_i=\max_{p=i-k}^{p\leq q} \{f_p+w_{p+1,i}\}=\max_{p=i-k}^{p\leq q} \{ \max \{f_p+w_{p+1,q} \} ,\max \{f_p + w_{q+1,i} \}\}\)
对于每一段，维护\(f_p+w_{p+1,q},f_p\)的后缀\(\max\)即可实现\(O(1)\)转移。
code
用dsu保证无后效性
对于有转移要求的树形dp（不知道别的行不行），可以重新建树，根据转移要求按一定顺序线性处理每个点，同时使用dsu维护当前节点已经做到的最后节点，处理连到就能走到的情形，具体看下面例题。
- P9352 [JOI 2023 Final] 训猫 / Cat Exercise 比较牛的题。首先注意到每次对于每个点只能去一个子树的性质，并且每次去的点权值比上一次小（对应上面的转移条件/顺序），我们直接根据权值建树，从小到大做，dsu维护做到现在与当前点连通的权值最大的点（注意在树上没有实际的祖先关系）。code
用维度推出维度/答案
几个有关联的与答案/限制相关的维度，不用全都记下来，用几个推出别的。
- U107556 河童重工，震撼人心 题目限制和A,B,总和都有关，只要保留两个就能推出第三个，一个放维度一个放答案。code
- P3126 [USACO15OPEN] Palindromic Paths G 回文两边同时跑还是挺经典的。我们关心目前的长度，两个端点的位置，注意到只要知道长度能得出目前x,y之和，所以只要记录一个就好。
对于等价的东西只关心数量，计入状态
特别用在概率dp中
- AT_dp_j Sushi 注意到值域很小而且当前数量一样的等价，把1/2/3的数量计入状态，0的可以用总数减一减推出，对应了上一条。令\(f_{i,j,k}\)为目前数量分别是i,j,k吃完要的期望步数（这种题好像都是把目标状态当作边界，目前还不知道为啥，总之想不出来正着反着都试试）。
\(f_{i,j,k}=\frac{n-i-j-k}{n}\times (f_{i,j,k}+1)+\frac{i}{n}\times (f_{i-1,j,k}+1)+\frac{j}{n} \times (f_{i+1,j-1,k}+1) +\frac{k}{n} \times (f_{i,j+1,k-1}+1)\) 然后移项得\(f_{i,j,k}=\frac{n}{i+j+k} \times(\frac{i}{n}\times f_{i-1,j,k}+\frac{j}{n} \times f_{i+1,j-1,k} +\frac{k}{n} \times f_{i,j+1,k-1}+1).\) 这种看起来有后效性的柿子，尝试改变枚举顺序，从小到大分别枚举k,j,i即可。
转移点相对固定，预处理排序构造单调性
可以这么用的关键在于一个转移点只和一维状态有关。
- P10282 [USACO24OPEN] Smaller Averages G
直接设划分到哪里，然后注意到一个转移点固定另一个是一端前缀，且随着第一个转移点的变化另一个的变化具有单调性，double-pointer+前缀和优化即可。哦 上面是没读清楚题的错误示范。发现原来是平均值，根本没有单调性啊！那我们就强行构造单调性。注意到以i为右端点的所有区间平均值都是固定的，那么对于i把所有可行的转移点j根据[j+1,i]平均值排序。转移的时候double-pointer（两个序列均单调），但是是固定一个转移点，另一个在转移序列上的一端前缀，如果前缀的这一维是内层循环的转移点，即这个序列是不固定的，就没有办法做前缀和。为了使其固定，考虑把前缀的那一维放到外层循环的转移点，枚举内层转移点，然后就可以预处理前缀和了。具体见code
状压\(3^n\)枚举子集，\(3^n\)枚举两个不交集合！
for (int S=1;S<(1<<n);S++) for (int T=S;T;T=(T-1)&S)for (int S=1;S<(1<<n);S++){int R=(((1<<n)-1)^S);for (int T=R;T;T=(T-1)&R)}
- P3959 [NOIP 2017 提高组] 宝藏 n小m大，经典形式。比较巧妙的一点是往上合并可能并到上上层，但注意到这样肯定是把这个点放到上一层更优，不影响答案。
状压：一些转移条件可以预处理
- P10975 Mondriaan's Dream 转移条件是(i&j)==0 且 (i|j)没有两个相邻的0。对于第二点可以预处理。
注意观察在dp变化过程中转移点的变化
特别用在二维（？），也可以通过改变转移顺序使其变得有特点。
- P3120 [USACO15FEB] Cow Hopscotch G
非A A的限制较紧 -> 容斥
- P3120 [USACO15FEB] Cow Hopscotch G
当设计的状态转移缺少信息但不能直接把该信息加进来时，加入一些钦定的意义
- P4182 [USACO18JAN] Lifeguards P 设\(dp_{i,j}\)为前i个删除了j个的最大覆盖长度，显然不好转移；如果加入覆盖的状态就爆炸了。删去被包含无意义的线段之后，有左端点升序时右端点也升序的性质，所以可以改成\(dp_{i,j}\)前i个删除了j个，钦定选了i不删的最大覆盖长度。但是这样设如果答案是最后一个不选就无了，所以在所有线段后面加上一条\([1e9,1e9]\)即可。
分讨展开max
当一个决策内部有max时可以尝试分讨展开
- P4182 [USACO18JAN] Lifeguards P \(dp_{i,j}=\max_{k<i}dp_{k,j-(i-k-1)}+r_i-\max(l_i,r_k)=\max_{ k<i} \begin{cases}dp_{k,j-(i-k-1)}+r_i-l_i & r_k<l_i\\ dp_{k,j-(i-k-1)}+r_i-r_k) & \text{otherwise}\end{cases}\)
对于case 1,只要求出前缀\(\max{dp_{k,j-(i-k-1)}}\)即可。对于case 2，单调队列维护\(\max dp_{k,j-(i-k-1)-r_k}\)。两者第一维的转移区间不交且并起来为\([0,i)\)，单调队列弹出的时候顺便把前面一个也维护了。考虑单调队列最好的性质在于单调，我们为了利用它可以尝试构造一些东西，比如说此题中第二个转移一开始和\(k,j-i+1(or \ j),i\)有关，为了利用这个k的单调性，可以把其中一个提出来拿掉（这里是i，因为转移的dp项和另两个有关，而i在转移时是定值），我们开\(O(n)\)个单调队列，第t个维护所有\(i-j=t\)的\(dp_{i,j}\) code（似乎还有一种分层转移，倒序枚举i-j的方法，只要开一个单调队列，但是没写）
当可行转移点是一段区间，转移过来的东西单调时，就直接找最左/最右的转移
单调可以根据意义判断。
- U112096 消息不可篡改 转移区间右端点是第一个能够包含当前待转移串的位置，如果往左移相当于是钦定了中间的都要删去，不优。找到右端点预处理在每个点前最靠后的每个字符位置，对于待转移串反着往前找一遍就行。
以及一些总结不出trick的选记
- CF2133F Flint and Steel 每个怪物有两种方式被打死：1.暴力打死。2.摔了损耗然后被打死。通过手玩样例将题目的形式转化成划分成几段，每一段左端点暴力打怪，然后剩余的从前到后依次打完。对于这些段落左端点显然从后到前打最优。从后往前dp消除后效性。套路地设\(f_i\)表示\([i,n]\)段分完打完的最小代价。写完柿子利用前缀和发现可以把和转移点有关的单独取出来且互不影响，维护一下后缀min就做完了。code
小专题：排列问题
经典形式是不给定排列，求满足某个条件的排列个数/权值之和。
考虑生成排列的集中方法：
- 从左到右依次确定当前数的相对大小。考虑这是一个动态的过程，每次把当前的当作一个排列（不管之后的），相对大小可以理解为在前缀中的排名，一次次在值域上插入。关键词是从左到右（位置），插入（相对）。
- AT_dp_t Permutation 题面很好地符合了两个关键词。\(dp_{i,j}\)即为做到第i个，第i个是前缀第j小。转移应该理解成，可以通过放置使得其处于j的位置，所以后大于前时\(dp_{i-1,j}\)也要转移进去。这个边界在这个生成方式中应该都挺重要的。
小专题：环形处理
-
做两次dp，第一次随便断，第二次钦定一些东西使得其等价于把第一次断开的位置强行连起来。
- P6064 [USACO05JAN] Naptime G 这种不能走到的初值要负无穷。\(dp_{0/1,i,j}\)前i个时间睡了j小时，第i小时有没有在睡觉，第一次dp没有限制，\(dp_{0,1,0}=dp_{1,1,1}=0\)，最后取\(\max(dp_{n,m,0},dp_{n,m,1})\)；第二次钦定睡1，n小时，\(dp_{1,1,1}=u_1\)，最后取\(dp_{n,m,1}\)。
-
复制一遍扔到后面。注意双倍空间。
- P10957 环路运输 这里的取max和绝对值可以，控制范围在\(\frac n 2\)和右减左去掉。然后化柿子记得把和相同变量相关的放到一起。直接单调队列优化即可。