[ABC145F] Laminate
阅读原文时间:2023年08月22日阅读:1

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)\)

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章