CodeForces 1131G. Most Dangerous Shark
2024-08-24 03:26:32
题目简述:从左到右依次有$n \leq 10^7$个Domino骨牌,高度为$h_i$,手动推倒他的花费为$c_i$。每个骨牌之间的距离为$1$。一个骨牌可以被向左或者向右推倒。当第$i$个骨牌被推倒时,他会以相同方向推倒与其距离$<h_i$的所有骨牌。求推倒所有骨牌的最小花费。
解:code
令$L[i], R[i]$分别表示第$i$个骨牌向左(右)推倒后,会将$(L[i], i]$($[i, R[i])$)区间内的骨牌推倒。这个可以用单调栈在$O(n)$时间内解决。
令$f[i]$表示(只通过推倒前$i$个骨牌来)推倒前$i$个骨牌的最小花费,则对$1 \leq i \leq n$,
$$ f[i] = \min\left\{ f[L[i]]+c_i, \min_{j < i < R[j]} \{f[j-1]+c_j\} \right\}, $$
这个动态规划也能用单调栈在$O(n)$时间内解决。
最新文章
- u-boot移植 III
- 自学一个月的java了
- hdu4915 Parenthese sequence 贪心O(n)解法(new)
- jQuery调用后台方法
- SonarQube的安装、配置与使用
- [置顶] Jquery学习总结(二) jquery选择器详解
- 深入理解javacript之prototype
- Android学习之Activity初步
- pyqt 简单判断指定的内容强度(比如帐号)
- Azure File SMB3.0文件共享服务(5)
- HBASE学习笔记--API
- day05(数字类型,字符串类型,列表类型)
- java-猜数字
- 【原创】Windows上应用程序报错常用分析方法总结
- 20165235 祁瑛 2018-4 《Java程序设计》第八周学习总结
- web项目错误—Java.util.ConcurrentMidificationException
- Windows 下的文件被占用问题解决
- css基础 -文本溢出 text-overflow:ellipsis;
- 线程面试top50题
- 渐变显示渐变消失的BackgroundView