题目分类列表 当前分类: 动态规划 (通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
1585 [USACO Dec05]清理牛棚 USACO 动态规划 线段树 clean 1 s 256 MiB ★★☆ 简单对比 36 90 40%
1584 [CTSC 2007]挂缀 动态规划 贪心 pendant 1 s 256 MiB ★★ 简单对比 31 58 53.45%
1581 [POJ2152]消防站 POJ 动态规划 树形DP poj_2152 1 s 256 MiB ★★★ 简单对比 19 37 51.35%
1571 搭配购买 最小生成树 并查集 动态规划 背包问题 buy 1 s 256 MiB ★☆ 简单对比 121 237 51.05%
1562 [POI 2002]滑雪者 图论 动态规划 skiers 1 s 256 MiB ★★☆ 简单对比 6 7 85.71%
1561 [WC 1999]迷宫改造 动态规划 最短路 rebuildmaze 10 s 128 MiB ★★★☆ 简单对比 1 4 25%
1558 [ZOJ 1638]贪婪之岛 动态规划 网络流 greedyisland 5 s 256 MiB ★★★☆ 简单对比 12 41 29.27%
1530 [UVa 1501] 修建长城 UVa 动态规划 状态压缩 constructthegreatwall 1 s 256 MiB ★★★★ 简单对比 2 3 66.67%
1529 [UVa 1094] 修筑水道 动态规划 插头DP 状态压缩 UVa channel 1 s 256 MiB ★★★★ 简单对比 1 1 100%
1528 [UVa 11276] 神奇的七 动态规划 快速幂 插头DP 状态压缩 矩阵运算 稀疏表 UVa magicalseven 2 s 256 MiB ★★★★☆ 简单对比 3 15 20%
1527 [UVa 11741] 网格覆盖 动态规划 状态压缩 矩阵运算 UVa 连通性 轮廓线DP ignoretheblocks 5 s 256 MiB ★★★ 简单对比 6 13 46.15%
1526 [UVa 1408] 飞行控制 动态规划 状态压缩 UVa flightcontrol 2 s 512 MiB ★★☆ 简单对比 1 1 100%
1525 [UVa 11443] 网格里的树 UVa 动态规划 状态压缩 插头DP treeinagrid 5 s 256 MiB ★★★☆ 简单对比 2 2 100%
1524 [UVa 12117] ACM谜题 动态规划 状态压缩 UVa acmpuzzle 1 s 256 MiB ★★☆ 简单对比 2 5 40%
1522 [POJ2441]安排公牛 POJ 位运算 动态规划 状态压缩 examnine 4 s 64 MiB ★★☆ 简单对比 34 89 38.2%
1521 [POJ1038]Bugs Integrated, Inc. 位运算 动态规划 状态压缩 POJ 轮廓线DP exameight 1 s 29 MiB ★★★ 简单对比 4 5 80%
1520 长方形骨牌覆盖 位运算 动态规划 状态压缩 examseven 5 s 256 MiB ★★☆ 简单对比 11 22 50%
1519 [SGU U131]Hardwood floors实木地板 位运算 动态规划 状态压缩 examsix 1 s 256 MiB ★★★ 简单对比 10 15 66.67%
1518 [POJ2411] Mondriaan's Dream POJ 位运算 动态规划 数学 状态压缩 examfive 3 s 64 MiB ★★ 简单对比 83 133 62.41%
1517 放国王 位运算 排列组合 状态压缩 动态规划 placeking 1 s 256 MiB ★★☆ 简单对比 122 358 34.08%