【NowCoder 补全计划】动态规划
NC21303 删除括号
给两个合法括号串 $s,t$，每次可以从 $s$ 删除一对相邻的括号 $()$，问是否可以从 $s$ 变成 $t$。
设 $f(i,j,k)$ 表示当前原串到 $i$，匹配串到 $j$，且原串略过 $k$ 个左括号（且这些左括号还未匹配），是否可能成立。
- 如果 $k=0$，且 $s_i=t_j$，那么 $f(i-1,j-1,k) \to f(i,j,k)$。
- 如果原串第 $i$ 位是 $($，那么 $f(i-1,j,k-1) \to f(i,j,k)$。
- 如果原串第 $i$ 位是 $)$，那么 $f(i-1,j,k+1) \to f(i,j,k)$。
最后判断 $f(lens,lent,0)$ 是否为 true 即可。时间复杂度 $\mathcal{O}(n^3)$。
NC21314 CodeForces
如果题目分数没有随时间变动，那么直接背包就好了。
但是现在不是这样，由于背包枚举物品是有次序的，如果两题都做，那么背包会默认优先做编号小的题目，这未必是最优的。
因此我们需要改变题目的枚举顺序，此处可以贪心。
假设当前两题 $i,j \ (i<j)$ 的分数减少速度是 $v_i,v_j$，做题时长为 $t_i,t_j$。
那么先做 $i$ 后做 $j$ 的损失是 $v_it_i + v_j(t_i+t_j)$，先做 $j$ 后做 $i$ 的损失是 $v_jt_j+ v_i(t_i+t_j)$。
我们想让损失变小，需要满足 $v_it_i + v_j(t_i+t_j) \le v_jt_j+v_i(t_i+t_j)$，化简得到 $v_jt_i \le v_it_j$。
按照这个顺序重排题目，就可以上背包了。
NC13249 黑白点
一棵全是白点的树，每次可以选择一个白点 $i$，将 $i$ 与 $1$ 的简单路径上距离小于 $k_i$ 的点全部染黑，问最少染多少次可以将树全部染黑。
首先有一个错误的贪心：叶子节点一定要染色，然后每次向上跳，跳到染不到的时候继续染色。
它错误的原因在于，$i$ 与 $1$ 路径上距离小于 $k_i$ 的点 $j$，可能有更大的 $k_j$，走得更远。
因此我们在从子节点上传到父节点时，要传递一个信息，就是当前是否需要被迫染色。
在还不急着染色的时候，我们在链上的每个点计入备选方案，等到必须染色时，把备选方案里从当前位置上升距离最远的点设置为染色点。
为了完成这个想法，我们记 $f(i)$ 表示当前还上升的最大空间（新的点染色前），$k(i)$ 记以当前的最远染色距离（所有备选方案的最远距离）。
对于父节点 $u$ 和子节点 $v$，有 $f(u) = \max\{f(v)-1\}$，$k(u)=\max(k(u),\max\{k(v)-1\})$。
如果当前 $f(u)=0$，代表此时必须要染色一个点，我们直接取出备选方案的最优解，即 $f(u)=k(u)$。
求出必须染色的点数即可。
NC21337 牛牛的回文串
你可以花费一定的代价在字符串加入指定字符、删除指定字符、转换指定字符。问构造出回文串的最小代价。
一眼DP，然后大力分讨：
- 首先转换指定字符可能存在间接转换，即 $a \to b, b \to c$ 的情况，这时我们需要像求 floyd 一样求出任意两个字符转换的最小代价。
- 假设 $c(i,j)$ 代表字符 $i \to j$ 的最小代价。像区间 DP 一样由外向内处理区间 $[i,j]$。
- 如果 $s_i=s_j$，我们可以无代价转移。
- 如果 $s_i \neq s_j$，选择以下这几种方案进行操作：
- 直接将 $s_i$ 转成 $s_j$，或 $s_j$ 转成 $s_i$；
- 将 $s_i$ 与 $s_j$ 都转成一个相同的字符；
- 将 $s_i$ 或 $s_j$ 直接删去其一；
- 在 $s_j$ 右侧插入一个与 $s_i$ 相同的字符；
- 在 $s_j$ 右侧插入一个与 $s_i$ 不同的字符，并将这个不同的字符转为 $s_i$；
- 在 $s_i$ 左侧插入一个与 $s_j$ 相同的字符；
- 在 $s_i$ 左侧插入一个与 $s_i$ 不同的字符，并将这个不同的字符转为 $s_j$；
时间复杂度可以做到 $\mathcal{O}(26n^2+26^3)$。