题目分类列表 当前分类: 斜率优化 (用平面上的点表示决策,并维护决策的凸包以降低DP的时间复杂度)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
3922 删除题目 李超线段树 斜率优化 delete 1 s 256 MiB ★★★★ 简单对比 2 4 50%
3837 [CEOI 2017] Building Bridges CDQ分治 动态规划 斜率优化 李超线段树 jiaqiao 1 s 256 MiB ★★★☆ 简单对比 1 1 100%
3828 [SDOI2012] 基站建设 CDQ分治 动态规划 平衡树 线段树 斜率优化 2012sdoi_jzjs 2.5 s 512 MiB ★★★☆ 简单对比 0 0 0%
3804 [JZOI 2022 day2]鲍勃打比赛 动态规划 斜率优化 jzoi2022_contest 4 s 256 MiB ★★★☆ 简单对比 2 2 100%
3711 社区规划 动态规划 斜率优化 community 2 s 256 MiB ★★★ 简单对比 5 16 31.25%
3700 [APIO2014]序列分割 斜率优化 sequencesegmentation 1 s 256 MiB ★★☆ 简单对比 2 4 50%
3665 [统一省选 2022]最大权独立集问题 HAOI 树形DP 斜率优化 mis 1 s 2048 MiB ★★★★☆ 简单对比 0 0 0%
3293 [CSP 2019S]划分 NOIP/CSP 区间DP 斜率优化 单调队列 2019partition 4 s 1024 MiB ★★★☆ 简单对比 6 38 15.79%
3135 [POJ 3709]K匿名序列 斜率优化 动态规划 k_anonymous 1 s 256 MiB ★★★ 简单对比 2 7 28.57%
3051 [NOIP 2018PJ]摆渡车 动态规划 NOIP/CSP 斜率优化 noip2018pj_bus 2 s 256 MiB ★★☆ 简单对比 24 209 11.48%
2723 [BZOJ 2726]任务安排3 二分法 动态规划 斜率优化 batch1 1 s 128 MiB ★★★☆ 简单对比 11 28 39.29%
2496 兰迪的私人写真 基本 贪心 动态规划 随机化 斜率优化 EOADcangshu 0.05 s 12 MiB ★☆ 简单对比 3 10 30%
2407 [NOI 2016]国王饮水记 动态规划 斜率优化 NOI2016drink 1.5 s 256 MiB ★★★★ 评测插件 0 8 0%
2225 [SDOI 2016 Round1] 征途 动态规划 决策单调性优化 斜率优化 menci_journey1 1 s 256 MiB ★★★☆ 简单对比 81 301 26.91%
2129 [APIO2010]特别行动队 斜率优化 动态规划 special 4 s 64 MiB ★★★ 简单对比 78 176 44.32%
1864 [国家集训队2011]设计铁路 斜率优化 nt2011_design 0.5 s 512 MiB ★★☆ 简单对比 20 34 58.82%
1859 [国家集训队2011]拆迁队 斜率优化 线段树 lanxisi 1 s 512 MiB ★★★★ 简单对比 23 91 25.27%
1768 [NOI 2014]购票 NOI 树分治 CDQ分治 树链剖分 计算几何 斜率优化 ticket 3 s 562 MiB ★★★★ 简单对比 47 297 15.82%
1701 [USACO Mar03]最大平均值 二分法 动态规划 斜率优化 USACO avanum 1 s 256 MiB ★★ 简单对比 67 149 44.97%
1664 [POJ 2841] 航海游戏 POJ 动态规划 单调队列 斜率优化 navigationgame 2 s 256 MiB ★★★☆ 简单对比 6 26 23.08%