[JXOI2017]数列(动态规划)

题面链接

题解

题目意思有点不好懂,其实就是在数列中找到与 $A_{i-1}$ 相邻的两项来限制 $A_i$ 的值,问方案数。

首先凭感觉,感觉越往后面的数可能的情况是更少的,整体呈收束趋势。

我们设用来更新 $A_i$ 的 $L$ 和 $R$ 为 $L_i$ 和 $R_i$ ,根据定义有 $L_{i-1} \leq A_{i-1} \leq R_{i-1}$ ,现在考虑更新 $A_i$ ,根据定义有 $L_{i-1} \le L_i \leq A_{i-1} $ , $R_{i-1} \ge R_i \ge A_{i-1}$ ,即$ L_{i-1} \leq L_{i}, R_{i-1} \geq R_{i}$ 。

这种收束的性质会为我们后面的dp转移提供便利。

考虑设计一个很朴素的状态,即 $f_{i,k,l,r}$ 表示当前填到第 $i$ 个数,$A_1$ 到 $A_{i-1}$ 中小于等于 $k$ 的最大的数为 $l$ ,大于等于 $k$ 的最小的数为 $r$

转移时有以下几种情况:

  1. $k,l,r$ 不相等, $A_{i-1}$ 要么是 $l$ 要么是 $r$ ,

$$f_{i, k, l, r} = \sum_{j \leq l} f_{i-1, l, j, r}+\sum_{j \geq r} f_{i-1, r, l, j}$$

  1. $k=l=r$

若 $A_{i-1}=k$ 那么$$f_{i,k, k, k} = \sum_{j \leq k} \sum_{z \geq k} f_{i-1,k, j, z}$$

否则,
$$f_{i,k,k,k}=\sum_{y\ne k}(\sum_{z\le y}f_{i-1,y,z,k}+\sum_{z\ge y}f_{i-1,y,k,z})$$
(y不等于k,不知道为什么latex乱掉了……)

这个 $O(nr_i^4)$ 的做法肯定会T,可以用前缀和达到 $O(nr_i^3)$ 计算发现过不了,但是实际上最大的点都能过,也许是我时间复杂度算错了吧。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注