首页 > 其他分享 >[ABC145F] Laminate

[ABC145F] Laminate

时间:2023-05-01 15:34:40浏览次数:47  
标签:ABC145F 题目 Laminate 比前 一列 该列

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

完成状态

已完成

标签:ABC145F,题目,Laminate,比前,一列,该列
From: https://www.cnblogs.com/OIerBoy/p/17366568.html

相关文章