@[CrashXrsy](/user/828573) $n \leq 1e6$ 显然不能 请使用贪心
by 02Ljh @ 2022-12-29 20:47:21
贪心，优先选结束早的。
by williamwei @ 2022-12-29 21:19:34
@[williamwei](/user/700558)
好的谢谢，本来想看看搜索行不行
by CurryNo_1 @ 2022-12-29 21:44:06
@[02Ljh](/user/578004)
请问一般时间和空间复杂度最大能是多少
by CurryNo_1 @ 2022-12-29 21:44:44
@[CrashXrsy](/user/828573) O(2^n)的 估计也就n<10吧
by 02Ljh @ 2022-12-29 22:31:18
@[CrashXrsy](/user/828573) 如果说不加优化的话就是 $\mathcal {O}(2^n)$，如果记忆化就看你搜索有几个维度，假如有两个维度那么复杂度是 $\mathcal {O}(n^2)$ 的。
by Nwayy @ 2022-12-30 07:07:52
@[winds888](/user/664744) 那不如动态规划，维护选和不选。
by williamwei @ 2022-12-30 17:34:01
@[williamwei](/user/700558) 能想出状转方程的情况下肯定动归啊......
by Nwayy @ 2022-12-30 17:36:14
正在验证$\texttt{dp}$方程，稍等...
by williamwei @ 2022-12-30 17:49:52
@[winds888](/user/664744)
设$f_{i,j}$为现在选到第$i$个数, 已选$j$个数的最大值，那么$f_{i,j} \gets \max(f_{i-1,j}, (f_{i-1,j-1} + 1) \times [a_i.st\geq a_{i-1}.ed])$
$f_{1,1} = 1$
$st$表示开始时间, $ed$表示结束时间
刚刚上课去了，抱歉。
by williamwei @ 2022-12-30 21:54:20