MENU

决策单调性

环上邮局 / 环上决策单调性

邮局 是决策单调性优化 dp 的经典应用,其属于限制段数的序列划分问题,可以通过二分队列 + wqs 二分的方式做到 $O(n\log L\log n)$,其中 $L$ 指的是坐标的值域,此处不多赘述。

Read More

Solution. LG5244 [USACO19FEB] Mowing Mischief P

Description

在 $T\times T$ 的正方形网格上(左下角格点坐标为 $(0,0)$,右上角为 $(T,T)$,共 $(T+1)^2$ 个格点),给定 $n$ 个关键点,保证横纵坐标都互不相同。要求选出尽可能多的关键点,使其按横坐标从小到大排序后,纵坐标也单调增。在此基础上,最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Read More

2023 笔记

Catalan 数

Catalan 数表示为 $C_n$,有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$,定义应该使用的是递推式。

Read More

决策单调性优化 dp 学习笔记

  • first version is written on 2022.3.30
  • updated on 2023.7.14:增加了例题,增加了二分栈板块。
  • updated on 2023.7.20:增加了大量例题。注意很多题是可以一题多解的。

公式较多,加载不出来的话试试检查-长按刷新-硬刷新。

Read More