YZOJ P1310 [省队训练][NOI模拟7]车的放置

时间限制：1000MS      内存限制：262144KB

难度：$8.0$

• 题目描述

有 $N$ 个 $1 \times h[i]$ 的矩形小棋盘，底边边长为 $1$，在一条直线上拼成了一个畸形的棋盘。

高度 $h[i]$ 给出，第 $i$ 个矩形的高为 $h[i]$，例如 $h = [3, 2, 4, 2]$ 的图形如下：

若两个车相互攻击仅当它们在同一列，或在同一行且在这一行它们之间棋盘格子都是存在的，例如上图中 $a$ 与 $b$ 是相互不攻击的，$c$ 与 $d$，$b$ 与 $c$ 均为相互攻击的。

现在要在这棋盘上放置恰好 $K$ 个相互不攻击的车，问有多少种方案。

• 输入格式

输入第 $1$ 行包括两个正整数 $N$，$K$，表示了棋盘的列数和放的车数。

第 $2$ 行包含 $N$ 个正整数，表示了棋盘每列的高度。

• 输出格式

输出包括一个非负整数，表示有多少种放置的方案，输出答案 $\mod 1000000007$ 后的结果即可。

• 样例输入

• 样例输出

• 数据规模与约定

对于 $100\%$ 的数据，有 $N \leq 500$，$K \leq 500$，$h[i]  \leq 1000000$ 。

 

 

 

---

 

 

 

把笛卡尔树建出来，在上面树形DP。

为了方便，在这里认为 笛卡尔树中的一个点 $i$ 表示的矩形 不包括它的所有子节点所表示的矩形，即这个矩形的宽为 $W=size_i$ ，高为 $H=h_{i}-h_{father}$ 。

设 $f_{i, j}$ 表示以 $i$ 为根的子树中放 $j$ 个车的方案数；$t_{i, j}$ 表示以 $i$ 为根的子树中放 $j$ 个车，并且这 $j$ 个车都不在 $i$ 表示的矩形中 的方案数。

那么有 $t_{i, j} = \sum\limits_{k=0}^{j}{f_{lson, k} \times f_{rson, j-k}}$ 。

还有 $f_{i, j} = \sum\limits_{k=0}^{j}{ t_{j-k} \times C_{H}^{k} \times C_{W-\left(j-k\right)}^{k} \times k!}$ 。

初始值 $f_{0, 0}=1$

时间复杂度 $O(nk^2)$