RainAir
My OI Blog
RainAir
「CF833B」The Bakery

题目大意

把 $n$ 个数分成 $k$ 个区间,每个区间的价值为区间内不同数字的个数,问价值和最大为多少。

题解

简单 dp:设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量,那么有转移

$$f_{i,j} = \min {f_{k,j-1}+cnt_{k+1,i}}$$

朴素的转移是 $O(n^3)$ 的,我们观察这个式子,如果固定 $j$ ,我们用线段树维护 $f_k+cnt_{k+1,i}$ 就可以达到 $O(logn)$ 的转移了。当 $i \to i+1$ 时我们只需要修改一下线段树 更新一下 $cnt$ 就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/781
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF833B」The Bakery
题目大意 把 $n$ 个数分成 $k$ 个区间,每个区间的价值为区间内不同数字的个数,问价值和最大为多少。 题解 简单 dp:设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。…
扫描二维码继续阅读
2019-08-26
标签
近期评论