RainAir
My OI Blog
RainAir
「BZOJ4906」「BJOI2017」喷式水战改

题目链接

题目大意是对于每种物品被划分到不同的组里会产生不同的贡献,求一种最大的划分(这里的划分是连续一段划分到一起),并且要动态维护这个东西。

我们首先考虑静态如何做这个东西,显然我们可以设出一个极为暴力的状态:$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用区间 $[i,j]$ 内的工作状态能得到的最大价值,直接 $O(4^3)$ 枚举中间点暴力转移一下就可以了。

但是我们还要支持插入呢,所以我们可以用平衡树来做这个东西,即用平衡树的节点表示一段区间 $[l,r]$ 的所有 dp 状态,这样就可以实现动态的修改和查询了。因为貌似并不是维护序列问题,所以我写了个替罪羊树,貌似也不是很慢(

代码:

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

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ4906」「BJOI2017」喷式水战改
题目链接 题目大意是对于每种物品被划分到不同的组里会产生不同的贡献,求一种最大的划分(这里的划分是连续一段划分到一起),并且要动态维护这个东西。 我们首先考虑静态如何做这个东…
扫描二维码继续阅读
2019-02-01
文章归档