Home avatar

Wings

深入理解期望DP

打牛客发现完全不会概率期望, 高中课本上的东西就是个屑, 大概率徐积限自己也不清楚就乱教. 冥思苦想, 用自己的方式理解了一波, 记录一下.

Codeforces Round 737 D.Ezzat and Grid

有 $n$ 个长度为 $10^9$ 的01串, 一个排在一行. 需要删去一些01串(行), 使得相邻两行中, 至少存在一列, 这一位上两个都是1.

01串由 m 个区间的形式给出, 三元组 $(i, l, r)$ 表示第 $i$ 个01串中, $[l,r]$ 区间上都是1.

求一个删除次数最少的方案.

$1 \le n, m \le 3 \cdot 10^5$

显然dp. 印象里早年在洛谷某次月赛做到过相似的题, 也是一行一行dp, 但是我忘记了, 有空回去补补.

设 $dp(i)$ 表示前 $i$ 行, 选第 $i$ 行, 能够留下来的最多多少行. 转移显然从能够相邻的前面的状态转移.

问题就在于, 如何快速知道, 哪些行可以和这一行相邻. 注意到第 $i$ 行的1是若干段连续的区间, 如果某一行和这些区间有交集, 那么就可以转移. 也就是说, 我们需要一个区间查询的操作. 这里就上线段树, 开一个大小为 $10^9$ 的线段树, 记录哪些点存在哪些行之类的信息. 做完一行时如果我们把当前行上1的区间加上当前行, 这样区间查询一下, 就知道可以从哪里转移了. 由于我们需要取最大值, 那么更小的点永远不会是决策点, 所以可以在点中记录 $dp(j)$ 的最大值, 同时记录决策点(因为需要方案), 然后区间查询最大值, 可以很方便地转移.