CF 1061 E

​ 还真没想到能这么做。

​ 每天都可以买票,第 i 天票价为 \(a_i\) 元,每张票在激活后都可以用 k 天,k 为给定常数,每天可以买多张票,可以任选每张票的激活时间。

​ 现在有 q 组询问,每组形如 l , r 表示只考虑第 l 天到第 r 天,要求每天都至少有一张票处于激活状态,求最小代价

​ 不难发现,答案的形式应该为 \(a_l+\min(a_l,a_{l+1},...,a_{l+k-1})+...\) ,而且考虑到 k 是常数,那么可以将下标按 mod k 同余分类

​ 现在假设一组内的下标为 \(h_1,h_2...h_m\) ,那么我想要求出 \(f_i\) = $\sum\limits_{k>=i}\min(h_i,...h_k) $

​ 这个的转移可以考虑处理出来 \(\text{suf}_i\) 表示 i 后面第一个小于 \(h_i\) 的位置,那么就有转移 \(f(i)=(suf_i-i)\times h_i+f(suf_i)\)

​ 现在有了 f 数组,那么考虑最终的答案应该如何用这个数组合并出来,用类似的思想,我们直接考虑 [l,r] 内和 l 在同一组的最小的 \(h_k\) ,设在同一组最大的下标为 j,求出这个可以用 ST 表。

​ 那么最后答案即为 \(f_i-f_k+h_k\times (j-k+1)\)

上一篇:一本通组合篇


下一篇:鸽巢原理学习