题目传送门
翻译
AtCoder
dp
引子:积木大赛
可以发现当 \(k=1\) 时,就是积木大赛。
但是如果后面那列比前面这列高,就需要考虑这一列是否需要改动。因为可以改成任意值,所以可以当成把这一列直接删掉,且不对两边产生影响。
问题变成了我们从 \(n\) 列中选 \(n-k\) 列,使其操作次数最少。
得到转移方程:\(f_{i,j}=\min\limits_{p=i+1}^nf_p,j-1+\min(0,h_i-h_p)\)
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章