分数: 600 点
问题陈述
有 N 树木从左到右排成一排。的 i第棵树 (1 \leq i \leq N) 从左起,树 i,高度为 H_i.
现在你将砍掉所有这些 N 树按照您喜欢的顺序排列。正式地,您将选择一个排列 P of (1, 2, \ldots, N) 并对每个执行以下操作 i=1, 2, 3, ..., N 按此顺序。
- 砍树 P_i,即设置 H_{P_i} to 0,成本为 H_{P_i-1}+H_{P_i}+H_{P_i+1}.
在这里,我们假设 H_0=0,H_{N+1}=0.
换句话说,砍伐一棵树的成本是砍伐前这棵树和邻近树木的总高度。
求排列数 P 最大限度地减少砍伐树木的总成本。由于计数可能很大,因此将其模数打印出来 (10^9+7).
约束
- 1 \leq N \leq 4000
- 1 \leq H_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N H_1 H_2 \ldots H_N
输出
打印排列数 P,模数 (10^9+7),最大限度地减少砍伐树木的总成本。
示例输入 1
3 4 2 4
示例输出 1
2
有两种排列 P 最小化总成本: (1,3,2) 和 (3,1,2).
下面,我们将展示砍伐树木的过程 例如 P=(1,3,2)。
- 首先,树 1 被削减,成本为 H_0+H_1+H_2=6.
- 接下来,树 3 被削减,成本为 H_2+H_3+H_4=6.
- 最后,树 2 被削减,成本为 H_1+H_2+H_3=2.
产生的总成本为 14.
示例输入 2
3 100 100 100
示例输出 2
6
示例输入 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
示例输出 3
54537651
请务必打印模数计数 (10^9+7).