【集训】W4：动态规划字符串
【集训】W4：动态规划字符串
登录以参加训练计划
- D1：基础动态规划（背包、区间）
- D2：图上动态规划（树形DP、DAG上DP）
- D3：概率与期望基础概念、概率DP
- D4~5：较难经典动规（状压DP、数位DP、动态规划经典优化）
- D6~7：实用字符串（哈希、KMP、字典树、manacher）
章节 101. 动态规划入门
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P5739 【深基7.例7】计算阶乘 | 40 | 20 | 1 |
| D0541 1.5.1 [IOI1994]数字三角形 Number Triangles | 127 | 69 | 3 |
| D0133 Frog 1 | 92 | 37 | 5 |
| D0134 Frog 2 | 87 | 35 | 5 |
| D0135 Vacation | 75 | 38 | 3 |
| D0136 Knapsack 1 | 98 | 38 | 5 |
| D0137 Knapsack 2 | 86 | 32 | 5 |
| D0445 01背包问题 | 152 | 55 | 5 |
| D0446 01背包输出方案 | 81 | 35 | 4 |
| D0447 完全背包问题 | 111 | 49 | 4 |
| D0430 最长上升子序列（n1000） | 149 | 69 | 4 |
| D0431 求最长不下降序列（n200） | 121 | 51 | 5 |
| D0432 最长公共子序列（n200） | 109 | 51 | 4 |
| D0709 合并果子 | 154 | 66 | 4 |
| 493 合并石子 | 154 | 65 | 5 |
| 799 「一本通 5.1 例 1」石子合并 | 155 | 57 | 5 |
| 800 「一本通 5.1 例 2」能量项链 | 95 | 50 | 3 |
| 802 「一本通 5.1 练习 1」括号配对 | 111 | 50 | 4 |
| P17015 [GESP202606 七级] 消消乐 | 12 | 5 | 5 |
| P1077 [NOIP 2012 普及组] 摆花 | 61 | 26 | 3 |
章节 102. 图上动态规划
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| JLOI2014E 松鼠的新家 | 141 | 50 | 5 |
| P1352 没有上司的舞会 | 47 | 27 | 5 |
| P2015 二叉苹果树 | 33 | 23 | 6 |
| P1273 [CHCI 2002 Final Exam #2] 有线电视网 | 24 | 14 | 6 |
| P2986 [USACO10MAR] Great Cow Gathering G | 28 | 11 | 6 |
| P5658 [CSP-S 2019] 括号树 | 57 | 12 | 6 |
| BZOJ4919 [Lydsy1706月赛]大根堆 | 43 | 16 | 5 |
| P4017 最大食物链计数 | 66 | 28 | 5 |
| P3128 [USACO15DEC] Max Flow P | 41 | 24 | 6 |
| P1122 最大子树和 | 61 | 22 | 5 |
| P2014 [CTSC1997] 选课 | 31 | 19 | 6 |
| P4438 [HNOI/AHOI2018] 道路 | 17 | 7 | 6 |
| P2585 [ZJOI2006] 三色二叉树 | 12 | 6 | 6 |
| P1040 [NOIP 2003 提高组] 加分二叉树 | 13 | 11 | 6 |
| P3177 [HAOI2015] 树上染色 | 40 | 15 | 7 |
| P4577 [FJOI2018] 领导集团问题 | 28 | 16 | 9 |
章节 100. LIS与LCS扩展
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| D0357 最长上升子序列长度（简单版） | 51 | 30 | 3 |
| D0358 最长上升子序列长度 | 82 | 35 | 4 |
| D0359 最长上升子序列方案 | 58 | 18 | 6 |
| D0360 最长不上升子序列长度 | 26 | 16 | 4 |
| D0361 最长上升奇偶子序列 | 41 | 19 | 4 |
| D0362 最长上升子序列方案数 | 35 | 18 | 4 |
| D0363 最长公共子序列长度 | 59 | 30 | 3 |
| D0364 排列的最长公共子序列长度 | 38 | 18 | 4 |
| D0365 反向最长公共子序列 | 29 | 23 | 2 |
| D0366 最长公共子序列方案 | 23 | 15 | 4 |
| D0367 字母的最长公共子序列 | 39 | 13 | 6 |