冒泡ioa
冒泡ioa

[JXOI2017]数列(动态规划)

题面链接

题解

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

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

我们设用来更新 A_iLRL_iR_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_1A_{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) 计算发现过不了,但是实际上最大的点都能过,也许是我时间复杂度算错了吧。

代码

发表评论

textsms
account_circle
email

冒泡ioa

[JXOI2017]数列(动态规划)
题面链接 题解 题目意思有点不好懂,其实就是在数列中找到与 $A_{i-1}$ 相邻的两项来限制 $A_i$ 的值,问方案数。 首先凭感觉,感觉越往后面的数可能的情况是更少的,整体呈收束趋势…
扫描二维码继续阅读
2019-05-09