记录一下自己学习提高课的过程，方便以后复习；
另外宣传一下我的 写题解工具，希望对大家有帮助。

动态规划

1. 数字三角形模型

模板题：AcWing 898. 数字三角形

• AcWing 1015. 摘花生
• AcWing 1018. 最低通行费
• AcWing 1027. 方格取数
• AcWing 275. 传纸条

2. 最长上升子序列模型

模板题：
1. AcWing 895. 最长上升子序列
2. AcWing 897. 最长公共子序列

• AcWing 1017. 怪盗基德的滑翔翼
• AcWing 1014. 登山
• AcWing 482. 合唱队形
• AcWing 1012. 友好城市
• AcWing 1016. 最大上升子序列和
• AcWing 1010. 拦截导弹
• AcWing 187. 导弹防御系统
• AcWing 272. 最长公共上升子序列

3. 背包模型

3.1 $01$ 背包

模板题：AcWing 2. 01背包问题

• AcWing 423. 采药
• AcWing 1024. 装箱问题
• AcWing 426. 开心的金明
• AcWing 734. 能量石

$01$ 背包问题求方案数

• AcWing 278. 数字组合
• AcWing 11. 背包问题求方案数「背包问题求最优解方案数」

$01$ 背包问题求具体方案

• AcWing 12. 背包问题求具体方案

3.2 二维费用背包

• AcWing 8. 二维费用的背包问题
• AcWing 1022. 宠物小精灵之收服「看完必懂」
• AcWing 1020. 潜水员

3.3 完全背包

模板题：AcWing 3. 完全背包问题

• AcWing 1023. 买书

完全背包求方案数

• AcWing 1021. 货币系统
• AcWing 532. 货币系统

3.4 多重背包

模板题：
1. AcWing 4. 多重背包问题
2. AcWing 5. 多重背包问题 II

• AcWing 1019. 庆功会
• AcWing 6. 多重背包问题 III 「TODO」

3.5 分组背包

模板题：AcWing 9. 分组背包问题

• AcWing 1013. 机器分配
• AcWing 487. 金明的预算方案

3.6 混合背包

• AcWing 7. 混合背包问题

3.7 有依赖的背包问题

• AcWing 10. 有依赖的背包问题

4. 状态机模型

基础课：AcWing 285. 没有上司的舞会

• AcWing 1049. 大盗阿福
• AcWing 1057. 股票买卖 IV
• AcWing 1058. 股票买卖 V
• AcWing 1052. 设计密码「TODO, 状态机 $DP$ + $KMP$」
• AcWing 1053. 修复DNA「TODO, $AC$ 自动机 + $KMP$」

5. 状态压缩 $DP$

基础课：
1. AcWing 291. 蒙德里安的梦想
2. AcWing 91. 最短Hamilton路径

• AcWing 1064. 小国王
• AcWing 327. 玉米田
• AcWing 292. 炮兵阵地
• AcWing 524. 愤怒的小鸟「TODO」
• AcWing 529. 宝藏「TODO」

6. 区间 $DP$

模板题：AcWing 282. 石子合并

• AcWing 1068. 环形石子合并
• AcWing 320. 能量项链
• AcWing 479. 加分二叉树
• AcWing 1069. 凸多边形的划分
• AcWing 321. 棋盘分割

7. 树形 $DP$

模板题：AcWing 285. 没有上司的舞会

• AcWing 1072. 树的最长路径
• AcWing 1073. 树的中心
• AcWing 1075. 数字转换
• AcWing 1074. 二叉苹果树
• AcWing 323. 战略游戏
• AcWing 1077. 皇宫看守

搜索

1. Flood Fill

• AcWing 1097. 池塘计数
• AcWing 1098. 城堡问题
• AcWing 1106. 山峰和山谷

2. 最短路模型

• AcWing 1076. 迷宫问题
• AcWing 188. 武士风度的牛
• AcWing 1100. 抓住那头牛

3. 多源 BFS

• AcWing 173. 矩阵距离

4. 最小步数模型

• AcWing 1107. 魔板

5. 双端队列广搜

• AcWing 175. 电路维修

6. 双向广搜

• AcWing 190. 字串变换

7. A*

• AcWing 178. 第K短路
• AcWing 179. 八数码

8. DFS 之连通性模型

• AcWing 1112. 迷宫
• AcWing 1113. 红与黑

9. DFS 之搜索顺序

• AcWing 1116. 马走日
• AcWing 1117. 单词接龙
• AcWing 1118. 分成互质组

10. DFS 之搜索顺序

• AcWing 165. 小猫爬山
• AcWing 166. 数独
• AcWing 167. 木棒「各种剪枝优化 + 剪枝证明 （看完必懂）+ 详细代码注释」
• AcWing 168. 生日蛋糕「TODO」

11. 迭代加深

• AcWing 170. 加成序列

12. 双向 DFS

• AcWing 171. 送礼物

13. 双向 DFS

• AcWing 180. 排书
• AcWing 181. 回转游戏「TODO」

图论

1. 单源最短路的建图方式

• AcWing 1129. 热浪
• AcWing 1128. 信使
• AcWing 1127. 香甜的黄油
• AcWing 1126. 最小花费
• AcWing 920. 最优乘车
• AcWing 903. 昂贵的聘礼

2. 单源最短路的综合应用

• AcWing 1135. 新年好
• AcWing 340. 通信线路
• AcWing 342. 道路与航线
• AcWing 341. 最优贸易「TODO」

3. 单源最短路的扩展应用

4. Floyd算法

• AcWing 1125. 牛的旅行
• AcWing 343. 排序
• AcWing 344. 观光之旅「TODO」
• AcWing 345. 牛站「TODO」

5. 最小生成树

• AcWing 1140. 最短网络
• AcWing 1141. 局域网
• AcWing 1142. 繁忙的都市
• AcWing 1143. 联络员「按照 p 和 w 升序排列，更简洁的写法」
• AcWing 1144. 连接格点

6. 最小生成树的扩展应用

• AcWing 1146. 新的开始
• AcWing 1145. 北极通讯网络
• AcWing 346. 走廊泼水节
• AcWing 1148. 秘密的牛奶运输

7. 负环

• AcWing 904. 虫洞
• AcWing 361. 观光奶牛
• AcWing 1165. 单词环「TODO」

8. 差分约束

• AcWing 1169. 糖果
• AcWing 362. 区间
• AcWing 1170. 排队布局
• AcWing 393. 雇佣收银员「TODO」

9. 最近公共祖先

• AcWing 1172. 祖孙询问
• AcWing 1171. 距离
• AcWing 356. 次小生成树「TODO」
• AcWing 352. 闇の連鎖「TODO」

10. 有向图的强连通分量

• AcWing 1174. 受欢迎的牛「思路详解 + 详细注释」
• AcWing 367. 学校网络
• AcWing 1175. 最大半连通子图「TODO」
• AcWing 368. 银河「TODO」

11. 无向图的双连通分量

• AcWing 395. 冗余路径
• AcWing 1183. 电力「TODO」
• AcWing 396. 矿场搭建「TODO」

12. 二分图

• AcWing 257. 关押罪犯
• AcWing 372. 棋盘覆盖「TODO」
• AcWing 376. 机器任务「TODO」
• AcWing 378. 骑士放置「TODO」
• AcWing 379. 捉迷藏「TODO」

13. 欧拉回路和欧拉路径

14. 拓扑排序

• AcWing 1191. 家谱树
• AcWing 1192. 奖金
• AcWing 164. 可达性统计
• AcWing 456. 车站分级「TODO」

高级数据结构

并查集

• AcWing 1250. 格子游戏
• AcWing 1252. 搭配购买
• AcWing 237. 程序自动分析
• AcWing 239. 奇偶游戏「TODO」
• AcWing 238. 银河英雄传说

基础算法

位运算

• AcWing 90. 64位整数乘法

递推与递归

• AcWing 95. 费解的开关「TODO」
• AcWing 97. 约数之和「TODO」
• AcWing 98. 分形之城「TODO」

前缀和与差分

• AcWing 99. 激光炸弹
• AcWing 100. 增减序列

二分

• AcWing 102. 最佳牛围栏
• AcWing 113. 特殊排序「TODO」

排序

• AcWing 105. 七夕祭「TODO」
• AcWing 106. 动态中位数
• AcWing 107. 超快速排序

RMQ

• AcWing 1273. 天才的记忆

参考文献

• 算法提高课