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

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

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注