题目分类列表 当前分类: 动态规划 (通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
1652 [POJ2931][MIT2005]拖延游戏 动态规划 博弈论 POJ procrastination 5 s 256 MiB ★★☆ 简单对比 1 1 100%
1649 [SPOJ 699] 巨大的背包 动态规划 贪心 SPOJ hugeknapsack 1 s 256 MiB ★★ 简单对比 5 21 23.81%
1629 [SGU U385]高地人游戏 动态规划 概率与期望 highlander 0.25 s 256 MiB ★★★ 简单对比 7 13 53.85%
1625 [POJ 1322] Chocolate POJ 动态规划 数学 概率分析 母函数/生成函数 poj1322_chocolate 2 s 256 MiB ★★★ 评测插件 13 30 43.33%
1624 [SGU U390]售票 分治 动态规划 数学 sgu390_tickets 1 s 256 MiB ★★ 简单对比 5 9 55.56%
1607 [UVa 1025] 城市里的间谍 动态规划 UVa uva_1025 1 s 256 MiB ★★★ 简单对比 11 26 42.31%
1598 [SDOI 2009]学校食堂 状态压缩 动态规划 贪心 dining 1 s 256 MiB ★★★ 简单对比 90 195 46.15%
1590 [USACO Feb14] 奶牛的十项全能 USACO 位运算 动态规划 状态压缩 deca 1 s 256 MiB ★★★ 简单对比 47 60 78.33%
1587 [CEOI2002][POJ1037]A decorative fence 动态规划 POJ decorative 1 s 1024 MiB ★★★ 简单对比 5 33 15.15%
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 ★☆ 简单对比 119 234 50.85%
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 2 100%
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%