102095: [AtCoder]ABC209 F - Deforestation
Description
Score : $600$ points
Problem Statement
There are $N$ trees standing in a row from left to right. The $i$-th tree $(1 \leq i \leq N)$ from the left, Tree $i$, has the height of $H_i$.
You will now cut down all these $N$ trees in some order you like. Formally, you will choose a permutation $P$ of $(1, 2, \ldots, N)$ and do the operation below for each $i=1, 2, 3, ..., N$ in this order.
- Cut down Tree $P_i$, that is, set $H_{P_i}$ to $0$, at a cost of $H_{P_i-1}+H_{P_i}+H_{P_i+1}$.
Here, we assume $H_0=0,H_{N+1}=0$.
In other words, the cost of cutting down a tree is the total height of the tree and the neighboring trees just before doing so.
Find the number of permutations $P$ that minimize the total cost of cutting down the trees. Since the count may be enormous, print it modulo $(10^9+7)$.
Constraints
- $1 \leq N \leq 4000$
- $1 \leq H_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $H_1$ $H_2$ $\ldots$ $H_N$
Output
Print the number of permutations $P$, modulo $(10^9+7)$, that minimize the total cost of cutting down the trees.
Sample Input 1
3 4 2 4
Sample Output 1
2
There are two permutations $P$ that minimize the total cost: $(1,3,2)$ and $(3,1,2)$.
Below, we will show the process of cutting down the trees for $P=(1,3,2)$, for example.
- First, Tree $1$ is cut down at a cost of $H_0+H_1+H_2=6$.
- Next, Tree $3$ is cut down at a cost of $H_2+H_3+H_4=6$.
- Finally, Tree $2$ is cut down at a cost of $H_1+H_2+H_3=2$.
The total cost incurred is $14$.
Sample Input 2
3 100 100 100
Sample Output 2
6
Sample Input 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
Sample Output 3
54537651
Be sure to print the count modulo $(10^9+7)$.
Input
题意翻译
$n$ 个数：$a_1,a_2,...,a_n$。 每次可以选择一个 $i$，选择的代价是 $a_{i-1}+a_i+a_{i+1}$，然后令 $a_i=0$。 求有多少种方案，使得 $a_1,a_2,...,a_n$ 都变为 $0$ 的总代价最小。特别的，$a_0=a_{n+1}=0$。Output
问题描述
从左到右有$N$棵树。从左数第$i$棵，即树$i$，高度为$H_i$。
现在你要按照你喜欢的顺序砍倒所有$N$棵树。形式上，你需要选择一个$(1, 2, \ldots, N)$的排列$P$，并按照以下顺序进行操作：
- 砍倒树$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)$取模。
限制条件
- $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
有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)$取模输出计数。