CF1209E2 Rotate Columns (hard version)
CF1209E2 Rotate Columns (hard version)。
这道题是用了贪心和状压 dp。
首先这道题需要一个贪心，就是不是每一个列都有用，只需要选最大值前 大的列，因为 比 小太多了。
然后再进行状压 dp。
表示现在到了第 列，然后行的填补状态为 。
然后转移过程中需要用到的 表示列的位移可以任意选择，对于行的集合为 的能做出的最大贡献。
转移方程式：dp[i][j] = max(dp[i-1][j], dp[i-1][k] + w[k^j] for all k⊆j)。
总结一下，这里的思路关键就是我们不知道这一行需要哪一列做最大值，所以要枚举每一列加入对哪些行做出贡献，相当于枚举对应关系。
看上去十分暴力。
CF1922F Replace on Segment
注意细节，不要打太快然后打错字符。
C++
状态压缩 dp
看到 包不包含 这种东西，可以用 0/1 表示，也可以分两个数组
f[l][r][j][1] 表示在 l 到 r 中都为 j 的最小代价
f[l][r][j][0] 表示在 l 到 r 中都不为 j 的最小代价
f[l][r][j][1] = f[l][r][j][0] + 1
f[l][r][j][0] = f[j][r][k][0] + 1 (k != j)
f[l][r][j][1] = f[l][mid][j][1] + f[mid+1][r][j][1]
f[l][r][j][0] = f[l][mid][j][0] + f[mid+1][r][j][0]