列举网站建设的基本流程,网站多大,wordpress自动换行,苏州高端网站建设咨询题目简述#xff1a;从左到右依次有$n \leq 10^7$个Domino骨牌#xff0c;高度为$h_i$#xff0c;手动推倒他的花费为$c_i$。每个骨牌之间的距离为$1$。一个骨牌可以被向左或者向右推倒。当第$i$个骨牌被推倒时#xff0c;他会以相同方向推倒与其距离$h_i$的所有骨牌。…题目简述从左到右依次有$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)$时间内解决。转载于:https://www.cnblogs.com/TinyWong/p/10427161.html
