题目分类列表 当前分类: 动态规划 (通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
25 [NOIP 2007]守望者的逃离 动态规划 NOIP/CSP 贪心 escape 1 s 128 MiB ★★ 简单对比 555 1656 33.51%
24 [HAOI 2007]修筑绿化带 动态规划 HAOI 递推 单调队列 parterre 1 s 128 MiB ★★★ 简单对比 76 177 42.94%
18 [NOI 2007]生成树计数 NOI 动态规划 递推 数学 快速幂 矩阵运算 状态压缩 插头DP CTS论文相关 count 1 s 128 MiB ★★★★☆ 简单对比 57 190 30%
16 [NOI 2007]货币兑换 NOI 动态规划 平衡树 分治 CDQ分治 斜率优化 cash 1 s 128 MiB ★★★★ 简单对比 189 651 29.03%
6 线型网络 图论 随机化 NP问题 数位DP 动态规划 linec 1 s 256 MiB ★★☆ 简单对比 165 1077 15.32%