Deforestation

题目描述

有 $N$ 棵树从左到右排成一行。第 $i$ 棵树 $(1 \leq i \leq N)$（记为树 $i$）的高度为 $H_i$。 你现在要按照任意你选择的顺序将这 $N$ 棵树全部砍倒。形式化地，你将选择一个 $(1,2,\ldots,N)$ 的置换 $P$，并按以下顺序对每个 $i=1,2,3,\ldots,N$ 执行操作。

砍倒树 $P_i$，即将 $H_{P_i}$ 设为 $0$，花费为 $H_{P_i-1}+H_{P_i}+H_{P_i+1}$。

这里，我们假设 $H_0=0,H_{N+1}=0$。 换句话说，砍倒一棵树的代价是砍倒之前该树及其邻居树的高度之和。 求使砍倒所有树的总代价最小的置换 $P$ 的数量。由于计数可能非常大，输出其对 $(10^9+7)$ 取模的结果。

输入格式

输入从标准输入给出，格式如下： $N$ $H_1$ $H_2$ $\ldots$ $H_N$

输出格式

输出使总代价最小的置换 $P$ 的数量，对 $(10^9+7)$ 取模。

3
4 2 4

2

3
100 100 100

6

15
804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764

54537651

提示

$1 \leq N \leq 4000$ $1 \leq H_i \leq 10^9$ 输入中的所有数值均为整数。有两个置换 $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$。
记得输出对 $(10^9+7)$ 取模的计数。

标签: AtCoder|abc209F

来源

AtCoder|abc209F