从另一个网站上的我的博客里转的。感觉放在一起比较好。时间久远，而且是英文（流泪）。

Easy Climb

Step 1

If \(x_i,d\le 100\).

Then define \(dp_{i,j}\) as the minimum cost for the first \(i\) stacks, with \(j\) as the height of the \(i^{\tt{th}}\) stack.

Then, the formula is very simple.

• \(dp_{i,j}=\displaystyle\min_{k=\max\{0,j-d\}}^{\min\{300,j+d\}}\{dp_{i-1,k}\}\)

But the time complexity is \(O(n^2d)\), so it will TLE.

Step 2

Observation 1

Define \(h_i'\) as the final value of the height of stack \(i\).

Then, \(h_i'\in\{h_{j \ (1\le j \le n)}+x (-n\le x\le n)\cdot d\}\).

Proof for Obervation 1

Consider the case when \(h_i'\notin\{h_{j \ (1\le j \le n)}+x (-n\le x\le n)\cdot d\}\). Let's discuss a specific example for simpicity.

If there is a tuple \(h_{i-1}\), \(h_i\) and \(h_{i+1}\) where \(h_{i-1}-h_i>d\) and \(h_{i+1}-h_i>d\). Then, if you want to adjust their heights, the cost-least way is to \(h_i \rightarrow \min\{h_{i-1},h_{i+1}\}-d\). Then, if you have an answer that isn't \(h_{i-1}+x\cdot d\) or \(h_{i+1}+x\cdot d\), the answer will become larger, which is easy to prove.

The other cases are simmilar to this one, so the observation is true as the case when \(h_i'\notin\{h_{j \ (1\le j \le n)}+x (-n\le x\le n)\cdot d\}\) is never the minimum answer.

With this observation, we can think of an \(O(n^5)\) code.

Step 3

Try optimizing \(O(n^5)\) into \(O(n^3)\). It is easy to notice that we can use a monotonous queue to optimize \(O(n^2)\) into \(O(1)\) and thus the whole complexity \(O(n^3)\).

Code