总算是补上了很久之前的坑，一直没学，之前一直不肯动脑子？
思路可以从简单的进行入手
对于部分DP，若转移是\(i\)从一个\(j\)转移过来，且转移具有单调性，切极为明显，形如\(f_i=max(f_i,f_j+b_j+a_i)\)
那么显然可以直接求之前的最值，用一个max记录即可
但是有时候会出现跟双方都有关的贡献项，使得没法直接取极值
如\(f_i=max(f_i,f_j+b_j+a_i+c_jd_i)\)
这样可以通过一些变式实现单调转移
举个例子，玩具装箱，洛谷P3195，典中典
首先易得\(O(n^2)\)DP，发现其转移式子较长，为方便，可以先将其化为\((a_i-b_j)^2\)的形式，方便化简，其中\(a\)是只与\(i\)有关的项，b是与\(j\)有关的以及一些常数项，方便书写和处理
发现拆括号后变成\(f_i=f_j+a_i^2+b_j^2-2a_ib_j\)
其中一部分只与i有关，一部分只与j有关，另一部分与i，j都有关，于是分类一下得\(2a_ib_j+f_i-a_i^2=f_j+b_j^2\)
发挥人类智慧，可以发现，变形后这类似一次函数形式，因为DP时固定i，\(f_i-a_i^2\)是定值，看作\(b\)，而\(2a_ib_j\)又类似\(kx\)的形式
因为\(2a_i\)也是定值，所以将\(b_j\)视作\(x\)，
（未更完）
标签：24,max,有关,2024,103rd,ib,转移,DP,2a From： https://www.cnblogs.com/tlz-place/p/18459492