DP入门2024.3.9
dp的精髓在于设计表格进行填写，即一个状态能由前一个状态转移，且一个状态已经求出，永不改变，即无后效性。同时满足最优子结构，即整体最优，则局部最优，比如路径a->b->c->d->e最优，则b->c->d 最优，否则也不会走b->c->d了
至于填表格，可以一行一列地填（01背包），也可以斜着填（区间dp)，填写方法总体分为两类：填表法，刷表法。填表法即顺推，比如f[i]=f[i-1]+f[i-2].刷表法：f[i]会影响f[i+1],f[i+2]所以对于每个f[i] ,f[i+1]+=f[i],f[i+2]+=f[i],对于明确知道能由那些状态推出时，用填表法，只知道能推得的其他状态，用刷表法，因题而异。
https://www.luogu.com.cn/problem/AT_dp_e 一看w太大，没法直接用背包求，却发现v好小，可以用v替换w那一维，此时第一步：设计表格完成了。那怎么利用表格呢？想，我们已经知道v对应的w了，肯定v越大，w越大，那么求出得到v的最小的w,从后往前遍历，得出最大的v且w<W(容量），即为答案
*****这个方法叫换维度
https://www.luogu.com.cn/problem/AT_arc073_b 看到v,w,都很大，想减小，发现wi-w1<=3,则每个都减去w1,用01背包，但是计算w是就是sum(选的个数）*w1+j 我们要知道sum,因为就算减去w1的部分的和为0，那万一是好多个w1加起来呢，于是另开一维度，记录选了多少个,求maxx时，枚举sum和j，判断是否<W即可，注意，同一个i，j越大，越容易>W,但i的上限可能小于j的上限，不能break掉两个for循环
https://www.luogu.com.cn/article/4ob4kqi2
思路见这个大佬博客https://www.luogu.com.cn/article/4ob4kqi2
就是说要有正方形，至少(i,j)(i-1,j)(i,j-1)(i-1,j-1)为1， 我们按照这个顺序由已知推未知状态： 分别是由左上，上，左三个点为已知的红色正方形，我们加上两个蓝色长方形就是一个大正方形。
我们只要满足大正方形成立就行了，也就是说，对于(i-1,j)(i,j-1)(i-1,j-1)，只要其中一个的正方形包含了两个蓝色长方形，大正方形就成立，那我们只要确保红色正方形边长为(i-1,j)(i,j-1)(i-1,j-1)各自正方形的最小值，这个大正方形必定成立，由于选其他正方形为红色正方形都无法证明蓝色长方形都为1，所以这就是最优解，大正方形边长为红色正方形边长+1，so:f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1])+1;
看看这道题的进阶https://www.luogu.com.cn/problem/P1681
想到我们刚才求的满足大正方形都为1满足的是一种要求，黑白相间也是一种要求，思路类似？
(i-1,j)(i,j-1)(i-1,j-1)各自正方形的边长最小的正方形，由于其他两个正方形的边长>=它，要么边长为1，要么其他两个正方形覆盖这个小正方形，那么意味着两个蓝色小长方形与红色长方形配套地黑白相间，so:f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1])+1;
https://www.luogu.com.cn/problem/P1754
****dp统计方案，这类题目通常由可转移的状态的方案数相加推得未知状态 即表示好状态，问题就解决了大半
对于此题，只有50元有用，A,B分别有j,k个，即j>=k, f[i][j][k]=f[i-1][j-1][k]+f[i-1][j][k-1] 第i个可能是A或B