What order of cutting down the trees is required to minimize the sum of costs?

First, for each tree let us consider how much its height contributes to the sum of costs. Such an approach of seeing the other way round is a common technique in competitive programming.

For the Tree \(i\) of height \(H_i\), let

• \(A_i\) be the number of times in which the height is added to the cost when cutting Tree \(i+1\),
• \(B_i\) be the number of times in which the height is added to the cost when cutting Tree \(i\), and
• \(C_i\) be the number of times in which the height is added to the cost when cutting Tree \(i-1\),

Then, \(B_i\) is always \(1\) regardless of the order of cutting down. \(A_i\) is \(1\) if Tree \(i\) is cut down after cutting Tree \(i+1\); otherwise it is \(0\). \(C_i\) is \(1\) if Tree \(i\) is cut down after cutting Tree \(i-1\); otherwise it is \(0\).

Therefore, for each \(i\,(1 \leq i \leq N-1)\),

• if Tree \(i\) is cut down after cutting Tree \(i+1\), \(H_i\) is added to the cost; otherwise \(H_{i+1}\) is.

Therefore, the cost is minimum if and only if for all \(i\,(1 \leq i \leq N-1)\),

• if \(H_i < H_{i+1}\), then Tree \(i+1\) is cut down before Tree \(i\) is;
• if \(H_i > H_{i+1}\), then tree \(i\) is cut down before Tree \(i+1\) is.

Next, we will explain how to find the total number of orders of cutting down that satisfy those constraints. It can be found in the following DP (Dynamic Programming):

• \(dp_{i,j}=\,(\)The number of all permutations of the first \(i\) trees such that Tree \(i\) is the \(j\)-th element to be cut down\()\).

The transitions will be as follows.

• if \(H_i=H_{i+1}\), then \(dp_{i+1,j}= \sum_{k=1}^{i} dp_{i,k}\);
• if \(H_i<H_{i+1}\), then \(dp_{i+1,j}= \sum_{k=j}^{i} dp_{i,k}\);
• if \(H_i>H_{i+1}\), then \(dp_{i+1,j}= \sum_{k=1}^{j-1} dp_{i,k}\).

While naive transitions cost a total of \(Θ(N^3)\) time, it can be optimized by means of cumulative sums so that it is solved in a total of \(O(N^2)\) time. Such a construction of DP where elements are inserted for every transition is called “insertion DP.”

Similar problem: https://atcoder.jp/contests/dp/tasks/dp_t