O(n^2) 树形背包
(zzs讲课没听, vp遭殃)
(zzs讲课没听, vp遭殃)
打牛客发现完全不会概率期望, 高中课本上的东西就是个屑, 大概率徐积限自己也不清楚就乱教. 冥思苦想, 用自己的方式理解了一波, 记录一下.
太弱小了! 没有力量!
太弱小了! 没有力量!
有 $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)$ 的最大值, 同时记录决策点(因为需要方案), 然后区间查询最大值, 可以很方便地转移.
不会暴力, 分块好难.
太弱小了! 没有力量! FFT 慢慢学叭先补题写记录, 不然要被大大骂惨了嘤嘤嘤.