题解 P2612 【[ZJOI2012]波浪】

2019-04-26 15:21:20


$\mathrm{DP}$ 。

发现绝对值不太好搞,把它拆掉。那么我们把 $1\sim n$ 从小到大插入序列中。

假设我们已经把 $1\sim i-1$ 都插进去了,考虑怎么算 $i$ 的贡献。

$i$ 的贡献分两边计算:

  • 如果 $i$ 的一边与边界相邻,该边有 $0$ 的贡献。
  • 如果 $i$ 的一边比 $i$ 小,那么该边有 $i$ 的贡献。
  • 如果 $i$ 的一遍比 $i$ 大,那么该边有 $-i$ 的贡献。

但是比 $i$ 大的还没有插进来,所以要强制 $i$ 与前面的 $i-1$ 个数和边界的相邻情况,这样才能算出 $i$ 的贡献。

那么就可以设状态了。设 $f[i][j][k][l]$ 表示前 $i$ 个数,有 $j$ 个连通块,前面的数的总贡献为 $k$ ,有 $l$ 个边界已经和某个数相邻的方案数。这里 $k$ 的范围是 $-4500\sim 4500$ 。

有 $5$ 种转移:

  • 一边与连通块相邻,一边不与连通块相邻。那么会产生 $0$ 的贡献,方案数为 $2\times j-l$ 。条件为 $j\neq 0$ 。

  • 两边都与连通块相邻。那么会产生 $2i$ 的贡献,方案数为 $j-1$ 。条件为 $j\geq 2$ 。

  • 两边都不与连通块相邻。那么会产生 $-2i$ 的贡献,方案数为 $j-l+1$ 。

  • 一边与边界相邻,一边不与连通块相邻。那么会产生 $-i$ 的贡献,方案数为 $2-l$ 。

  • 一边与边界相邻,一边与连通块相邻。那么会产生 $i$ 的贡献,方案数为 $2-l$ 。条件为 $j\neq 0$ 。

转移时要注意不要出现超出范围的下标。答案为 $\frac{\sum\limits_{i=m}^{4500}f[n][1][i][2]}{n!}$ 。

接着是一些问题:

  • 因为 $k$ 可以取负数,所以 $k$ 那一维要加上 $4500$ 。
  • 空间会炸,所以 $i$ 要滚动数组。
  • 本题需要数据分治: $K\leq 8$ 时要用 $\mathrm{double}$ , $K\leq 30$ 时要用 $\mathrm{\_\_float128}$ 。可以写两个 $\mathrm{subtask}$ 或者写 $\mathrm{template}$ 。

另外 $k$ 取 $-5000\sim 5000$ 在 $\mathrm{BZOJ}$ 上会 $\mathrm{MLE}$ ?取 $-4500\sim 4500$ 就能过了?

具体实现及细节见代码