板刷cf dp

来源https://www.luogu.com.cn/training/3963#problems
一句话题解(废话连篇题解)
CF296B Yaroslav and Two Strings
显然，分类讨论， 可以容斥 计算三种情况 只有等的a3 只有大于等于的a1 只有小于等于 a2 显然ans=cnt总-a1-a2 a3 也可以dp 状态dp[i][sta] sta 有四种情况 不可比拟的，满足大于等于条件的，满足小于等于条件的，只满足等于条件的，分情况讨论转移 处理起来比较麻烦
CF362C Insertion Sort
首先确定一点 泡沫排序的最小交换次数是逆序对数，任何交换一对数都可以暴力枚举，然后如何确定前后的影响，因为数据范围小（5000）可以预处理f1[i][j] 前j位前缀和小于第i位数，f12[i][j] 前j位前缀和大于第i位数，然后暴力枚举 这对数 i ,j ,计算影响即可
CF229D Towers
贪婪是不可能的(？太他妈贪心了)
状态普通dp[i] 最小合并次数为前i位 ，但是还有一个隐藏的状态是第i位，第j位
[i,j]该区间合并，即两层循环
但转移条件是贪婪的 也就是说，在寻找j的时候，从后到前 只要满足 [i,j] 合并高度大于h[j-1]可以转移
CF223B Two Strings
死亡思维字符串
给你两个字符串s,t,判断是否满足于每一个s[i]，s的子序列是否存在s[i]且等于t
显然，如果是双指针i,j从前向后找的话，如果相等的话s[i]==t[j]显然可以将j ,但如果不等待(思维来了)，你应该找到出现在同一个字符前面的最后位置，也就是说aba 和ab匹配 当匹配到第二个a时，显然只能匹配到t串的一个位置，即最后一个a匹配位置出现在s串的前面，
这样，每个S串都可以预处理i最匹配t位置的前缀位置l[i]和后缀r[i]
然后再次遍历每个位置，如果l[i]>r[i]即使有一个字符不能凑出来
CF847E Packman
很像dp但是，你只会贪点，一个人吃包装显然需要从字符串左到右，记录左边剩余的包装位置lst，和已经到了右边pos如果遇到人，如果有lst你需要吃东西，然后把剩下的距离扩展到右边。至于你最多能扩展多少，有两种选择。先吃左边，确保你吃左边。如果没有，直接pos =x，走完字符串后发现pos>=n且！lst说明合法