Day2

感觉很像背包但是不知道怎么证的，但是感觉很对。

ARC104D。赛时思路很对啊，就是犯蠢了。

首先考虑枚举每个平均值 $x$，那么就等价于值域在 $[1,x-1]$ 的数，每个数可以选至多 $k$ 个的和 等于 值域在 $[1,n-x]$ 的数，每个数可以选至多 $k$ 个的和的 方案数。

考虑直接 dp，$f_{i,j}$ 表示值域为 $[1,i]$ 的数，和为 $j$ 的方案数，转移有 $f_{i,j}=\sum_{t=0}^k f_{i-1,j-it}$，时间是 $\text{O}(n^3k^2)$，过不去，考虑前缀和优化 dp 转移，时间复杂度 $\text{O}(n^3k)$。

神秘转化。

题目等价于对于所有的 $i \neq j$，都有 $a_i \leq a_j,b_i \leq b_j,c_i \leq c_j$ 或 $a_i \geq a_j,b_i \geq b_j,c_i \geq c_j$。

然后比较匪夷所思的一步是考虑把这个看成三维坐标系中的坐标，考虑 dp，令 $f_{i,j,k}$ 表示所有 $x \leq i,y \leq j,z \leq k$ 的 $(x,y,z)$ 使合法的最小代价，每次转移考虑使新的不合法的走到 $(i+1,j,k)/(i,j+1,k)/(i,j,k+1)$，前缀和预处理出点的个数，$\text{O}(1)$ 转移。

时间复杂度 $\text{O}(n^3)$。link

P7013/CF309E。

首先读完题套路的开始考虑二分答案：