洛谷秋令营Day5-进阶DP
杂题选讲
DP 把一堆状态当成一个等价类集合，一起转移
状压 DP：忽略集合中元素的顺序，比如把 n! 优化为 2^n
区间 DP：忽略区间具体是怎么拼起来的
DP 状态设计的不好：划分的集合里的东西没法一起转移，或者状态太碎了还能再合并一下
DP 题的难度确实高，2 小时讲了 5 道半题，除了两道水题之外基本都在讲剩下 3 道半题，讲高阶的 DP 课确实是不容易的，可能不如准备好讲课材料发下去自学好。
绿题
P4059，正贡献和负贡献都有，是否空格插入越多越不好？并不是的，因为负贡献有时候更坑。至多插空格的上限是多少？dp[i][j][k][l]，匹配进度是 i 和 j，两个段分别末尾有 k 和 l 的长度的空格。两个字符串同时在同一个位置加空格肯定更劣，所以 k 和 l 至少有一个是 0。我们注意到空格的贡献是关于连续空格段的一次函数，假如是正比例函数的话，那么直接把空格的贡献顺手加进来就好了。现在是一次函数，第一次插入空格时增加的是首项，后边每次加空格加的是公差，都是一样的。这样只需要 dp[i][j] 加上两个串后边谁有空格就好了。
ABC180E，数据范围很小，考虑状压，看上一个城市是谁就好了，状压裸题。唯一值得注意的点在于至少访问一次为什么只需要考虑成访问恰好一次，是因为三角不等式的存在。
P1220，考虑 dp[i][j][0/1]，关掉 (i, j) 之间的灯，最后停在左端点/右端点的最小代价，这是一个区间 DP。代价具体怎么算？这个需要后边做的时候仔细看一下。本题相当于用区间表示一个集合。
CF1882D，由于要枚举根，所以大概率需要换根，先看看根钦定为 1 的时候怎么做。最终每个数的值到底异或成谁呢？能否一定做到？考虑异或从下往上做，则一定能逐渐把每棵子树变得一样。 dp[i] 为把以 i 为根的数的值都变得和根一样的操作数。假如一棵子树里的数的值都还不一样，那只能先把这里面的变得一样才能继续往上做。关键在于这棵子树的值到底变成多少，我们可以先钦定变得和根一样（可以证明这样就是更好的），算一个代价，然后考虑换根求剩下的根的结果。
1 小时 20 分钟讲了 4 道绿题，看来 DP 确实有点难。
蓝题
P3646，枚举到底分成多少段，然后 dp[i][j] 考虑把前 i 个分成 j 段的最小值，但这个状态可能有后效性。注意到要想让 or 出来的某个位为 0，则每一段的这个位都得是 0，所以我们可以从高到低位枚举，看每个段能否最高位都是 0，能的话就让他是 0，再考虑更低的位。由于考虑后边的位的时候需要前面的位也得满足条件，所以需要带着前面的位搞。后边好像很困难了。
CF1515E，我们是否总可以先确定一个集合，然后从左到右把想手动打开的给打开呢？注意到 i - 1 和 i + 1 都打开之后自动打开的是中间的 i，而 i 不会影响其他灯的打开，所以可能可以先确定打开的灯的集合有多大以及方案，再考虑打开顺序的问题。
老师的思路是考虑到只能自动点亮中间的一个，所以自动开的灯一定不连续，所以可以考虑枚举被连续手动开的段，然后做一下。考虑前 i 个灯，j 个是手动开的，我们去枚举看最后一段手动开的灯有多少个，然后发现我们其实关心最后一个灯是不是手动开的，在状态中加一个 0/1 表示。dp[i][j][0] += dp[i - 1][j][1]（不可能有连续的两个不是手动开的），dp[i][j][1] += dp[k][j - (i - k)][0] * f(i - k)，其中 f(x) 代表为了将 x 盏灯都手动打开，有多少种方案数。下面考虑如何求 f(x)，我们必须得时刻保证打开的是连续的一段，于是有一种思路是枚举第一个灯打开的是谁，然后考虑往左往右打开，假设从第 i 个作为第一个，则类似网格图上走路的方案数，答案就是 C(x - 1, i - 1)。这个事情从 i = 1 求和到 i = x 其实就是 2^(x - 1)。这样复杂度就是 O(n^3)。但这样好像还是不完整，我们只考虑了每个段自己的顺序方案数，但我也可以某段的还没开完，直接去搞另一段的，这也会带来不同的顺序，这个如何计算呢？这里其实就是在做一个插空，这个事情其实就是 C(j, i - k) 的方案。