未完待续 CF1107E Vasya and Binary String 设 $f(i,j,t)$ 为删去区间 $[i,j]$，其中区间右边还有 $t$ 个与 $S[j]$ 相同的字符的最大收益。 $$f(i,j,t) = \max \begin{cases}f(i,j-1,0) + a_{t+1}\\max _{k=i}^{j-1} \Big\{…

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

luogu8551 Bassline 题目的限制翻译过来就是 $[x,y]$ 中任意位置都被覆盖了相同次数。 用差分求出每个点被覆盖的次数，双指针求极长的满足条件的位置即可。 #include<bits/stdc++.h> using namespace std; #define int long long #define uint u…

聊聊状态压缩。 顾名思义，就是把一个状态压成一个整数，从而使得问题的所有状态可以度量。 一般都是用二进制状态压缩来表示子集与全集的关系，对应着二进制每一位都是 $0$ 或 $1$。更高的进制能表示更多的信息，但状态的数量也会随之增加，并且实现的时候要自己手写位运算，较为复杂，本文不会涉及。 信息的表示 luogu7076 [CSP-S2020] 动…