CF908G

考虑每一位的贡献,对于数字 $x(x\in [0,9])$ ,若其在第 $i$ 位出现了 $k$ 次,那么贡献为 $k\times 10^i$ 。

现在需要求出 $k$ 。设 $f(i,x)$ 表示第 $i$ 位的数为 $x$ 的总方案数,不是很好求,考虑拆分,令 $g(i,x)$ 表示第 $i$ 位的数 $\geq x$ 的总方案数。

设 $dp(i,j,x,k)$ 表示填了前 $i$ 位,有至少 $j$ 个数字 $\geq x$ ,当前数字与 $n$ 的大小关系为 $k(k\in[0,1])$ ,转移枚举第 $i+1$ 位上的数字即可。

CF868F

考虑 $\rm{DP}$ ,设 $dp(i,j)$ 表示前 $i$ 个数分了 $j$ 段,转移很显然:

$$ f(i,j)=\min_k\{f(k,j-1)+w(k+1,i)\} $$

其中 $w(k+1,i)$ 为这一段的权值,可以用莫队求。

盲猜决策单调性,用分治优化即可。

ARC073F

考虑 $\rm{DP}$ ,设 $f(i,j)$ 表示到了第 $i$ 轮,一个数在 $x_{i-1}$ ,一个数在 $j$ 时的最小代价,有转移:

$$ f(i,x_{i-1})=\min_k\{f(i-1,k)+|k-x_i|\}\\ f(i,j)=f(i-1,j)+|x_{i-1}-x_i| $$

第二个转移很好处理,考虑第一个转移:

$$ f(i,x_{i-1})=\min_k\{f(i-1,k)+|k-x_i|\}\\ f(i,x_{i-1})=\min_k\begin{cases} [k\geq x_i]\ f(i-1,k)+k-x_i\\ [k< x_i]\ f(i-1,k)+x_i-k\\ \end{cases} $$

用两颗线段树优化即可。

ARC063F

显然即使整个矩阵布满了点,随便找一列或者一行也可以作为答案。

也就是说无论如何答案至少是 $\max(w+1,h+1)\times 2$ ,如论如何我们求出来的答案也不会低过这个下界。

考虑如果答案矩阵不经过 $x=W/2$ 或 $y=H/2$ ,那么其周长最多为 $w+h$ ,显然小于 $\max(w+1,h+1)\times 2$ ,也就是说答案矩阵一定经过 $x=W/2$ 或者 $y=H/2$ ,分别考虑即可,用 $x=W/2$ 作为例子:

考虑线上面的点,依次扫过所有点,用单调栈维护一下当前矩形的最大高度,然后用线段树维护,每次更新即可。


continue:

agc20E,arc93f,agc35e

最后修改:2019 年 12 月 30 日 07 : 22 PM