动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。
登录以参加训练计划
章节1：线性动态规划，即具有线性阶段划分的动态规划。
章节2：01背包问题：多种物品,每种物品只有一个.求能获得的最大总价值。我们考虑是否选择第i件物品时,是需要考虑前i-1件物品对答案的贡献的。
章节3：完全背包问题：此类背包问题中,我们的每种物品有无限多个,可重复选取。类似于01背包,我们依旧需要考虑前i-1件物品的影响.。
章节4：多重背包问题：此类问题与前两种背包问题不同的是,这里的物品是有个数限制的。(下面用𝑛𝑢𝑚[𝑖]表示物品i的个数）多个物品,我们就可以看成为一个大的物品,再去跑01背包即可.
章节5：其他背包问题：一般分组背包问题中,每组中只能选择一件物品。状态大家都会设𝑓[𝑘][𝑣]代表前k组物品构成体积为v的背包所能取得的最大价值和。但是我们每组物品中只能选择一件物品.
章节 1. 线性动态规划
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1216 [USACO1.5] [IOI1994] 数字三角形 | 6 | 5 | 10 |
| P1020 [NOIP1999 提高组] 导弹拦截 | 6 | 2 | 10 |
| P1091 [NOIP2004 提高组] 合唱队形 | 16 | 5 | 8 |
| P1095 [NOIP2007 普及组] 守望者的逃离 | 21 | 3 | 9 |
| P1541 [NOIP2010 提高组] 乌龟棋 | 2 | 1 | 10 |
| P1868 饥饿的奶牛 | 7 | 1 | 10 |
| P2679 [NOIP2015 提高组] 子串 | 0 | 0 | (无) |
| P2501 数字序列 | 0 | 0 | (无) |
| P3336 话旧 | 0 | 0 | (无) |
| P3558 BAJ字节计算机 | 0 | 0 | (无) |
| P4158 粉刷匠 | 0 | 0 | (无) |
| P5301 宝牌一大堆 | 0 | 0 | (无) |
章节 2. 01背包
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1048 [NOIP2005 普及组] 采药 | 5 | 5 | 10 |
| P1049 [NOIP2001 普及组] 装箱问题 | 9 | 5 | 9 |
| P1164 小A点菜 | 5 | 5 | 10 |
| P1060 [NOIP2006 普及组] 开心的金明 | 11 | 8 | 8 |
| P1064 [NOIP2006 提高组] 金明的预算方案 | 2 | 1 | 10 |
| P2946 [USACO09MAR] 牛飞盘队 | 1 | 1 | 10 |
| P1156 垃圾陷阱 | 0 | 0 | (无) |
| P2871 [USACO07DEC] 魅力手镯 | 8 | 4 | 10 |
| P1510 精卫填海 | 20 | 12 | 6 |
| P2639 [USACO09OCT] 贝西的重量问题 | 17 | 10 | 6 |
| P2925 [USACO08DEC] 干草待售 | 10 | 8 | 9 |
| P1926 小书童——刷题大军 | 25 | 10 | 6 |
| P1802 5 倍经验日 | 29 | 8 | 7 |
| P1734 最大约数和 | 1 | 1 | 10 |
| P2392 考前临时抱佛脚 | 1 | 1 | 10 |
| P1466 [USACO2.2] 集合 | 25 | 6 | 8 |
| P2370 小帅 的 U 盘 | 3 | 3 | 10 |
| P4141 消失之物 | 1 | 1 | 10 |
| P2340 [USACO03FALL] 奶牛展览 | 1 | 1 | 10 |
章节 3. 完全背包
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5662 [CSP-J2019] 纪念品 | 6 | 4 | 10 |
| P1616 疯狂的采药 | 34 | 8 | 7 |
| P2722 [USACO3.1] 总分 | 6 | 4 | 10 |
| P1853 投资的最大效益 | 15 | 4 | 9 |
| P2918 [USACO08NOV] 购买干草 | 23 | 4 | 8 |
| P1679 神奇的四次方数 | 2 | 2 | 10 |
| P1832 A+B Problem（再升级） | 2 | 1 | 10 |
| P5020 [NOIP2018 提高组] 货币系统 | 1 | 1 | 10 |
章节 4. 多重背包
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1833 樱花 | 1 | 1 | 10 |
| P5365 英雄联盟 | 0 | 0 | (无) |
| P1077 [NOIP2012 普及组] 摆花 | 1 | 1 | 10 |
| P2347 [NOIP1996 提高组] 砝码称重 | 1 | 1 | 10 |
| P6771 [USACO05MAR] 太空电梯 | 1 | 1 | 10 |
章节 5. 其他背包
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5322 排兵布阵 | 0 | 0 | (无) |
| P1855 榨取kkksc03 | 1 | 1 | 10 |
| P1507 NASA的食物计划 | 2 | 2 | 10 |
| P1541 [NOIP2010 提高组] 乌龟棋 | 2 | 1 | 10 |
| P1776 宝物筛选 | 0 | 0 | (无) |
| P1782 旅行商的背包 | 0 | 0 | (无) |
| P2732 [USACO3.3] 商店购物 | 0 | 0 | (无) |
| P2851 [USACO06DEC] 费西硬币 | 0 | 0 | (无) |
| P1757 通天之分组背包 | 16 | 5 | 8 |
| P1941 [NOIP2014 提高组] 飞扬的小鸟 | 0 | 0 | (无) |
| P1910 L 国的战斗之间谍 | 1 | 1 | 10 |
| P1877 音量调节 | 1 | 1 | 10 |
| P1509 成为好朋友 | 1 | 1 | 10 |
| P3985 不开心的金明 | 1 | 1 | 10 |
| P1455 搭配购买 | 2 | 2 | 10 |
| P2170 选学霸 | 3 | 3 | 10 |
| P2904 [USACO08MAR] 河流穿越 | 3 | 3 | 10 |
| P2623 物品选取 | 1 | 1 | 10 |
- 参加人数
- 9
- 创建人
-
吴老师 (MJAKlang)