较复杂的线性DP、非线性DP、DP的优化策略
Login to join training plan
DP进阶：
- 区间DP、环形DP
- 树形DP
- 数位DP
DP的优化策略：
- 优化状态表示：状压DP，等
- 优化状态转移（按下不表）
Section 1. 区间DP、环形DP
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1775 石子合并（弱化版） | 25 | 12 | 5 |
| P149 「一本通 5.1 例 1」石子合并 | 43 | 12 | 7 |
| P151 「一本通 5.1 例 3」凸多边形的划分 | 40 | 9 | 7 |
| P150 「一本通 5.1 例 2」能量项链 | 16 | 8 | 8 |
| P3205 [HNOI2010] 合唱队 | 38 | 11 | 7 |
| P154 「一本通 5.1 练习 3」矩阵取数游戏 | 7 | 3 | 10 |
| P4342 [IOI1998] Polygon | 23 | 5 | 8 |
| P4290 [HAOI2008] 玩具取名 | 30 | 9 | 7 |
| P4170 [CQOI2007] 涂色 | 23 | 7 | 7 |
Section 2. 树形DP
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P1122 最大子树和 | 30 | 11 | 6 |
| P155 「一本通 5.2 例 1」二叉苹果树 | 45 | 7 | 8 |
| P2014 [CTSC1997] 选课 | 43 | 10 | 7 |
| P1273 有线电视网 | 6 | 2 | 10 |
| P158 「一本通 5.2 例 4」战略游戏 | 32 | 9 | 7 |
| P159 「一本通 5.2 例 5」皇宫看守 | 42 | 5 | 9 |
| P1352 没有上司的舞会 | 15 | 9 | 7 |
| P164 「一本通 5.2 练习 5」骑士 | 56 | 6 | 9 |
| P1040 [NOIP2003 提高组] 加分二叉树 | 2 | 1 | 10 |
| P2585 [ZJOI2006] 三色二叉树 | 4 | 1 | 10 |
| P1070 [NOIP2009 普及组] 道路游戏 | 1 | 0 | 10 |
| P3478 [POI2008] STA-Station | 24 | 9 | 7 |
| P10974 Accumulation Degree | 18 | 2 | 9 |
Section 3. 数位DP
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P166 「一本通 5.3 例 2」数字游戏 | 25 | 9 | 7 |
| P171 「一本通 5.3 练习 4」数字计数 | 47 | 9 | 8 |
| P165 「一本通 5.3 例 1」Amount of Degrees | 6 | 3 | 10 |
| P167 「一本通 5.3 例 3」Windy 数 | 41 | 5 | 9 |
| P168 「一本通 5.3 练习 1」数字游戏 | 11 | 1 | 10 |
| P169 「一本通 5.3 练习 2」不要 62 | 0 | 0 | (None) |
| P170 「一本通 5.3 练习 3」恨 7 不成妻 | 0 | 0 | (None) |
Section 4. 状压DP
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P2622 关灯问题II | 8 | 1 | 10 |
| P8687 [蓝桥杯 2019 省 A] 糖果 | 2 | 1 | 10 |
| P172 「一本通 5.4 例 1」国王 | 28 | 8 | 7 |
| P1879 [USACO06NOV] Corn Fields G | 8 | 2 | 10 |
| P10447 最短 Hamilton 路径 | 1 | 1 | 10 |
| P1171 售货员的难题 | 2 | 1 | 10 |
| P10975 Mondriaan's Dream | 1 | 1 | 10 |
| P2704 [NOI2001] 炮兵阵地 | 1 | 0 | 10 |
| P3959 [NOIP2017 提高组] 宝藏 | 2 | 1 | 10 |
