题目分类列表 当前分类: 动态规划 (通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
340 [NOI 2005]瑰丽华尔兹 NOI 动态规划 单调队列 adv1900 1 s 128 MiB ★★★ 简单对比 166 502 33.07%
337 [NOI 2004]曼哈顿 NOI 动态规划 搜索法 manhattan 2 s 128 MiB ★★☆ 简单对比 3 13 23.08%
335 [NOI 2003]数据生成器 NOI 动态规划 图论 树形DP jerrygen 1 s 128 MiB ★★☆ 简单对比 25 66 37.88%
331 [NOI 2002]贪吃的九头龙 NOI 动态规划 dragon 1 s 128 MiB ★★☆ 简单对比 27 63 42.86%
327 排序集合 动态规划 递推 sort 1 s 128 MiB ★★ 简单对比 11 16 68.75%
326 医院设置 动态规划 图论 最短路 hospital 1 s 128 MiB ★☆ 简单对比 144 225 64%
324 诸侯安置 动态规划 递推 empire 1 s 128 MiB ★★ 简单对比 28 75 37.33%
321 [SCOI 2008] 着色方案 递推 动态规划 散列 FFT 记忆化搜索 容斥原理 组合数学 color 1 s 64 MiB ★★★ 简单对比 45 87 51.72%
319 [RQNOJ 184] 洞窟探索 动态规划 贪心 hole 1 s 128 MiB ★★★ 简单对比 21 73 28.77%
317 [HAOI 2008]玩具取名 HAOI 动态规划 name 1 s 128 MiB ★★★ 简单对比 128 276 46.38%
312 [HAOI 2007]上升序列 HAOI 动态规划 分治 LIS lis 1 s 128 MiB ★★☆ 简单对比 221 585 37.78%
308 [HAOI 2007]理想的正方形 HAOI 动态规划 稀疏表 单调队列 square 2 s 128 MiB ★★☆ 简单对比 246 587 41.91%
305 [HAOI 2008]木棍分割 动态规划 HAOI 分治 二分图 贪心 决策单调性优化 stick 3 s 128 MiB ★★★☆ 简单对比 165 460 35.87%
302 [HAOI 2008]硬币购物 数学 HAOI 动态规划 容斥原理 coin 1 s 128 MiB ★★★ 简单对比 92 150 61.33%
301 [NOI 2001]炮兵阵地 NOI 动态规划 状态压缩 位运算 cannon 5 s 256 MiB ★★☆ 简单对比 209 549 38.07%
300 [NOI 2001]陨石的秘密 NOI 动态规划 线性DP secret 1 s 128 MiB ★★★ 简单对比 78 167 46.71%
296 [NOI 2000]古城之谜 NOI 动态规划 字符串 lostcity 1 s 128 MiB ★★★☆ 简单对比 15 82 18.29%
291 [NOI 2008]设计路线 NOI 动态规划 图论 design 2 s 128 MiB ★★★★ 简单对比 26 57 45.61%
289 [NOI 2008]奥运物流 NOI 动态规划 图论 背包类树形DP 贪心 trans 1 s 128 MiB ★★★★ 简单对比 19 34 55.88%
285 [NOI 1999]最优连通子集 NOI 动态规划 图论 subset 1 s 128 MiB 简单对比 35 51 68.63%