Original link: https://blog.chungzh.cn/articles/abc-209f/
The meaning of the question: Given the height of $n$ trees, the cost of cutting the $i$th tree is $h_i+h_{i-1}+h_{i+1}$, how many schemes can be cut down? The total cost of all trees is the smallest.
The cost of cutting down a tree is only related to the height of adjacent trees. Next, we study the influence of the order of cutting $h_i$ and $h_{i+1}$ on the answer.
- Cut $h_i$ first and then cut $h_{i+1}$: $h_i+h_{i-1}+h_{i+1}+h_{i+1}+h_{i+2}$
- Cut $h_{i+1}$ first and then $h_i$: $h_{i+1}+h_i+h_{i+2}+h_i+h_{i-1}$
After making a difference, get: $h_{i+1}-h_i$. When $h_{i+1}>h_i$, $h_{i+1}$ should be cut first. When $h_{i+1}<h_i$, $h_i$ should be cut first. Therefore, for two adjacent trees, the one that is cut first is the best .
Insertion DP (insertion DP) : first consider the first $i-1$ number, and then insert the $i$th number in the middle.
Let $\mathit{f}_{i,j}$ represent the tree-cutting order of the first $i$ trees, and the $i$th tree is ranked at the $j$ position, and the number of solutions with the minimum cost is obtained .
When $h_{i+1} > h_i$, $i+1$ should be cut first, then $\mathit{f} {i+1,j} = \sum {k=j}^{i}\mathit {f}_{i,k}$
When $h_i > h_{i+1}$, $i$ should be cut first, then $\mathit{f} {i+1,j} = \sum {k=1}^{j-1}\mathit {f}_{i,k}$
When $h_i = h_{i+1}$, any tree can be cut, $\mathit{f} {i+1,j} = \sum {k=1}^i\mathit{f}_{i ,k}$
DP can be optimized with prefix sum, $O(n^2)$.
Mental error! : Subtraction forget to add MOD.
|
|
Thanks to ABC 209 F – Deforestation – hzy0227
This article is transferred from: https://blog.chungzh.cn/articles/abc-209f/
This site is only for collection, and the copyright belongs to the original author.