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)\)