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$。
按照这个顺序重排题目，就可以上背包了。
标签：背包,题目,补全,jt,原串,括号,那么,NowCoder,动态 From： https://www.cnblogs.com/HZSPZCR/p/18487777