23.12.9考试总结

分数 : $60$ （ $50+10+0+0$ )

A. stick

先是一个数字，然后一串 $0$ ，最后一串 $8$ 。贪就完了。

注意模数是 $998244$ 8 $53$ 。挂分 $50pts$

B. game

正解爆搜。少打 break挂 $90pts$ 。

答案很多，所以 $yes$ 跑得很快。

最坏情况 $5\times 6$ ，此时 $O(1^4\times2^{14}\times3^{16})$ 。

注意到数据很小，考虑可行性剪枝即可。

来自永远的7日之都 .

C. noip

万恶的 $O2$ ， $RE\ \ 0$ 。

字典序从大到小搜索, $DP$ 预处理 $每个后缀首字母确定的情况下所能得到的最大权值$ ，判断当前是否 $\geq\ x$ $(可行性剪枝)$ 。

学的是 $DP作为部分$ 的思路。

D. remove

区间 $DP$ 。求

min \left\{ \begin{aligned} a \times k + b\times\sum\limits_{i=1}^{k} \Big (max_i-min_i\Big) \end{aligned} \right\}

设方程 $f_{l,r,max,min}$ 表示消除区间 $[l,r]$ 使其剩下的最大值为 max ，最小值为 min 的最小代价。 $g_{l,r}$ 表示区间 $[l,r]$ 中全消的最小代价。

所以

初始化 :

$g_{l,r}=min$ { $f_{l,r,max,min}+a+b\times (r-l)^2$ }

转移

左边空或右边空 :

$f_{l,r,max,min}=\min\{g_{l,k} + f_{k+1,r,max,min}\}$

$f_{l,r,max,min}=\min\{g_{k+1,r} + f_{l,k,max,min}\}$

两边都空

$f_{l,r,max,min}=\min\{f_{l,r,max,min} + f_{k+1,r,max,min}\}$

端点刷表

$f_{l,r+1,max(max,w_l),min(min,w_r)}=f_{l,r,max,min}$

g?

$g_{l,r}=min$ { $f_{l,r,max,min}+a+b\times(max-min)^2$ }

离散化后 $O(n^4)$