主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：P10845 [EGOI2024] Bouquet / 花束制作
最后更新于 2025-08-28 08:45:17
作者
2huk
分类
题解
题解
P10845
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
考虑类似 LIS 的 DP。 令 $f(i)$ 表示只考虑前 $i$ 棵郁金香，且第 $i$ 棵一定选的方案数。 枚举上一个选的郁金香 $j$。 $$ \begin{matrix} f(i) = 1+\max f(j)&(j \le i - 1 \land i \ge j + r_j + 1 \land j \le i-l_i-1) \end{matrix} $$ 把后面那个条件化简一下得到 $j \le i - l_i - 1 \land j + r_j \le i - 1$。这是一个二维偏序的形式。二维树状数组即可。 注意到空间是 $\mathcal O(n^2)$ 的。但是实际用到的树状数组上的位置是 $\mathcal O(n \log^2 n)$ 级别的，也就是时间复杂度。于是可以直接用 `__gnu_pbds` 的 `gb_hash_table`。
正在渲染内容...
点赞
2
收藏
0
