题目分类列表 当前分类: 斜率优化 (用平面上的点表示决策,并维护决策的凸包以降低DP的时间复杂度)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
1463 [CF311B]Cats Transport 动态规划 斜率优化 cats_tran 1 s 128 MiB ★★★ 简单对比 3 3 100%
1441 [NOIP 2013]花匠 NOIP/CSP 动态规划 斜率优化 二分法 模拟 单调队列 树状数组 线段树 贪心 数学 FlowerNOIP2013 1 s 128 MiB ★★☆ 简单对比 388 991 39.15%
1330 [HNOI 2008]玩具装箱toy 动态规划 斜率优化 决策单调性优化 bzoj_1010 1 s 256 MiB ★★★ 简单对比 202 418 48.33%
1162 [POJ 1180]任务安排2 斜率优化 动态规划 poj1180_batch 1 s 128 MiB ★★☆ 简单对比 4 13 30.77%
376 [IOI 2002] 任务安排 动态规划 斜率优化 batch 1 s 128 MiB ★★☆ 简单对比 121 237 51.05%
367 [ZJOI 2007] 仓库建设 动态规划 斜率优化 ZJOI storage 1 s 128 MiB ★★★ 简单对比 115 260 44.23%
363 [USACO Mar08] 土地购买 USACO 动态规划 斜率优化 决策单调性优化 acquire 1 s 128 MiB ★★★ 简单对比 143 415 34.46%
362 [CEOI2004]锯木厂选址 动态规划 单调队列 斜率优化 随机化 two 0.1 s 32 MiB ★★★☆ 简单对比 126 287 43.9%
16 [NOI 2007]货币兑换 NOI 动态规划 平衡树 分治 CDQ分治 斜率优化 cash 1 s 128 MiB ★★★★ 简单对比 189 651 29.03%