2023-02-25
题目
翻译
难度&重要性(1~10):6
题目来源
AtCoder
题目算法
dp
解题思路
引子:积木大赛
可以发现当 \(k=1\) 时，就是积木大赛。
- 该列比前一列高：此时会产生 \(h_i-h_{i-1}\) 的贡献。
- 该列比前一列矮或相等：此时不会产生贡献。
但是如果后面那列比前面这列高，就需要考虑这一列是否需要改动。因为可以改成任意值，所以可以当成把这一列直接删掉，且不对两边产生影响。
问题变成了我们从 \(n\) 列中选 \(n-k\) 列，使其操作次数最少。
得到转移方程：\(f_{i,j}=\min\limits_{p=i+1}^nf_p,j-1+\min(0,h_i-h_p)\)
完成状态
已完成