acwing-提高课

Myth丶恋晨 2022-09-07 06:15 153阅读 0赞

**目录**

递归

递推

数学

贪心

子序列

线段树

树形dp

区间dp

数位dp

破环成链

可持久化

背包问题

斜率优化

状态压缩dp

状态机模型

单调队列优化

单源最短路径

floyd算法及其变形

--------------------

# 递归 #

[记忆化搜索声明数组的技巧][Link 1]

# 递推 #

[1075 数字转换（python3 树形dp-树的最长路径、递推）][1075 _python3 _dp-]

[300 任务安排1（python3 动态规划）][300 _1_python3]

# 数学 #

[246 区间最大公约数（c++-java 线段树）][246 _c_-java]

[1075 数字转换（快速求解约数之和）][1075 _python3 _dp-]

# 贪心 #

[125 耍杂技的牛（python3 贪心）][125 _python3]

[1010 拦截导弹（python3 最长上升子序列扩展）][1010 _python3]

# 子序列 #

[895 最长上升子序列（python3）][895 _python3]

[1017 怪盗基德的滑翔翼（python3 最长上升子序列扩展）][1017 _python3]

[1014 登山（python3 最长上升子序列扩展）][1014 _python3]

[482 合唱队形（python3 最长上升子序列扩展）][482 _python3]

[1012 友好城市（python3 转化-最长上升子序列问题）][1012 _python3 _-]

[1016 最大上升子序列和（python3）][1016 _python3]

[1010 拦截导弹（python3 最长上升子序列扩展）][1010 _python3]

[187 导弹防御系统（python3 最长上升子序列 + dfs）][187 _python3 _ _ dfs]

[272 最长公共上升子序列（python3）][272 _python3]

# 线段树 #

[1275 最大数（c++-java 不带有懒标记的线段树）][1275 _c_-java]

[245 你能回答这些问题吗（c++-java 线段树）][245 _c_-java]

[246 区间最大公约数（c++-java 线段树）][246 _c_-java]

[243 一个简单的整数问题2（c++-java 线段树）][243 _2_c_-java]

[1277 维护序列（c++-java 线段树）][1277 _c_-java]这道题目包含了区间的加法和乘法，是一道关于两个懒标记的综合题目

# 树形dp #

[285 没有上司的舞会（python3 树形dp 三个辅助数组来建图）][285 _python3 _dp]

[1072 树的最长路径（python3 树形dp）][1072 _python3 _dp]

[1073 树的中心（python3 树形dp）][1073 _python3 _dp]

[1075 数字转换（python3 树形dp-树的最长路径扩展、递推）][1075 _python3 _dp-]

[1074 二叉苹果树（python3 树形dp）][1074 _python3 _dp]

[323 战略游戏（python3 树形dp）][323 _python3 _dp]

[1077 皇宫看守（python3 树形dp）][1077 _python3 _dp]

# 区间dp #

[区间dp问题][dp]

[282 石子合并（python3 区间dp）][282 _python3 _dp]

[1068 环形石子合并（python3 环形区间变成链的技巧）][1068 _python3]

[320 能量项链（python3 环形区间dp）][320 _python3 _dp]

[1069 凸多边形的划分（python3 区间dp + 高精度）][1069 _python3 _dp _]

[479 加分二叉树（python3 区间dp）当题目中还需要额外条件的时候可以使用额外的数组来记录最佳方案][479 _python3 _dp]

[321 棋盘分割（python3 高维区间dp 记忆化搜索）][321 _python3 _dp]

# 数位dp #

[数位dp总结（python3）][dp_python3]

[递推求解组合数Cxn（python3）][Cxn_python3]

[1081 度的数量（python3 数位dp）][1081 _python3 _dp]

[1082 数字游戏（python3 数位dp）][1082 _python3 _dp]

[1083 Windy数（python3 数位dp）][1083 Windy_python3 _dp]

[1084 数字游戏 II（python3 数位dp）][1084 _ II_python3 _dp]

[1085 不要62（python3 数位dp）][1085 _62_python3 _dp]

[1086 恨7不成妻（c++-python3 数位dp）][1086 _7_c_-python3 _dp]

# 破环成链 #

[1068 环形石子合并（python3 环形区间变成链的技巧）][1068 _python3]

[1088 旅行问题（python3 单调队列优化）][1088 _python3]

# 可持久化 #

[256 最大异或和（可持久化Trie树）][256 _Trie]

# 背包问题 #

[423 采药（python3 零一背包问题）][423 _python3]

[1024 装箱问题（python3 零一背包问题）][1024 _python3]

[3 完全背包问题（python3）][3 _python3]

[二维费用的背包问题（python3）][python3]

[1022 宠物小精灵之收服（python3 二维费用的零一背包问题）][1022 _python3]

[278 数字组合（python3 零一背包扩展求方案数目）][278 _python3]

[4 多重背包问题 I（python3 零一背包问题的扩展）][4 _ I_python3]

[1019 庆功会（python3 多重背包问题）][1019 _python3]

[1023 买书（python3 完全背包问题求方案数）][1023 _python3]

[背包问题体积限制的类型与空间优化问题][Link 2]

[1020 潜水员（python3 二维费用的零一背包问题）][1020 _python3]

[12 背包问题求具体方案（python3 零一背包问题求具体方案）][12 _python3]

[9 分组背包问题（python3）][9 _python3]

[1013 机器分配（python3 多重与分组背包问题扩展）][1013 _python3]

[487 金明的预算方案（c++-python3 分组背包问题扩展）][487 _c_-python3]

[426 开心的金明（python3 零一背包问题）][426 _python3]

[1021 货币系统（python3 完全背包问题求方案数）][1021 _python3]

[532 货币系统（python3 完全背包问题）][532 _python3]

[5 多重背包问题 II（python3 二进制优化-转为零一背包问题求解）][5 _ II_python3 _-]

[7 混合背包问题（python3）][7 _python3]

[10 有依赖的背包问题（c++-python3 分组背包问题 + 树形dp）][10 _c_-python3 _ _ _dp]

[11 背包问题求方案数（python3）][11 _python3]

[734 能量石（python3 贪心 + 零一背包问题）][734 _python3 _ _]

# 斜率优化 #

[300 任务安排1（python3 动态规划）][300 _1_python3]

[301 任务安排2（python3 斜率优化）][301 _2_python3]

[302 任务安排3（python3 斜率优化）][302 _3_python3]

# 状态压缩dp #

[状态压缩dp][dp 1]

[291 蒙德里安的梦想（python3 状态压缩dp）][291 _python3 _dp]

[1064 小国王（python3 状态压缩dp）][1064 _python3 _dp]

[327 玉米田（python3 状态压缩dp）][327 _python3 _dp]

[292 炮兵阵地（python3 状态压缩dp）][292 _python3 _dp]

[524 愤怒的小鸟（python3 状态压缩dp-集合式状态压缩dp）][524 _python3 _dp-_dp]

# 状态机模型 #

[1049 大盗阿福（python3 状态机模型）][1049 _python3]

[1057 股票买卖 IV（python3 状态机模型-滚动数组优化）][1057 _ IV_python3 _-]

[1058 股票买卖 V（python3 状态机模型）][1058 _ V_python3]

[1052 设计密码（python3 kmp + 状态机模型）][1052 _python3 kmp _]

# 单调队列优化 #

[单调队列优化总结][Link 3]

[135 最大子序和（python3 单调队列优化）][135 _python3]

[1088 旅行问题（python3 单调队列优化）][1088 _python3]

[1089 烽火传递（python3 单调队列优化）][1089 _python3]

[1090 绿色通道（python3 二分 + 单调队列优化）][1090 _python3 _ _]

[1087 修剪草坪（python3 单调队列优化）][1087 _python3]

[1091 理想的正方形（python3 单调队列优化）][1091 _python3]

# 单源最短路径 #

**在一个图中检查连通性可以使用下面的三种常见的方法：① dfs ② bfs ③ 并查集**

**单源最短路径的建图方式**

[单源最短路径相关算法总结][Link 4]

[python建图的三种常见方式][python]

[python多组测试数据的输入处理][python 1]

[849 Dijkstra求最短路 I（python3 朴素Dijkstra算法模板）][849 Dijkstra_ I_python3 _Dijkstra]

[850 Dijkstra求最短路 II（python3 堆优化版本的Dijkstra算法模板）][850 Dijkstra_ II_python3 _Dijkstra]

[851 spfa求最短路（python3 spfa求解最短路径）][851 spfa_python3 spfa]

[1129 热浪（python3 单源最短路径模板）][1129 _python3]

[1128 信使（python3 floyd算法）][1128 _python3 floyd]

[1127 香甜的黄油（python3 spfa求解最短路径）][1127 _python3 spfa]

[1126 最小花费（python3 单源最短路径扩展）][1126 _python3]

[920 最优乘车（python3 抽象--＞单源最短路径）][920 _python3 _--]

[903 昂贵的聘礼（python3 单源最短路径-建图）][903 _python3 _-]

**单源最短路径的综合应用：**

[1135 新年好（python3 单源最短路径 + dfs）][1135 _python3 _ _ dfs]

[340 通信线路（python3 单源最短路径 + 二分）][340 _python3 _ _]

[342 道路与航线（python3 单源最短路径 + 拓扑排序）][342 _python3 _ _]

[341 最优贸易（python3 单元最短路径 + dp）][341 _python3 _ _ dp]

**单源最短路径的扩展应用：**

[1137 选择最佳线路（python3 单元最短路径扩展-增加一个虚拟源点）][python 1]

[1131 拯救大兵瑞恩（python3 单源最短路径扩展-拆点(dp)）][1131 _python3 _-_dp]

[1134 最短路计数（python3 单源最短路径扩展-最短路计数）][1134 _python3 _-]

[383 观光（python3 单源最短路径扩展-次短路的求解）][383 _python3 _-]

# floyd算法及其变形 #

[多源多汇最短路][Link 5]

[1125 牛的旅行（python3 floyd算法的基础应用）][1125 _python3 floyd]

[343 排序（python3 floyd算法求解传递闭包）][343 _python3 floyd]

[344 观光之旅（python3 floyd算法求解最小环）][344 _python3 floyd]

[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120604795
[1075 _python3 _dp-]: https://blog.csdn.net/qq_39445165/article/details/120547789
[300 _1_python3]: https://blog.csdn.net/qq_39445165/article/details/120678505
[246 _c_-java]: https://blog.csdn.net/qq_39445165/article/details/119896730
[125 _python3]: https://blog.csdn.net/qq_39445165/article/details/120313150
[1010 _python3]: https://blog.csdn.net/qq_39445165/article/details/120343323
[895 _python3]: https://blog.csdn.net/qq_39445165/article/details/120322502
[1017 _python3]: https://blog.csdn.net/qq_39445165/article/details/120325948
[1014 _python3]: https://blog.csdn.net/qq_39445165/article/details/120335229
[482 _python3]: https://blog.csdn.net/qq_39445165/article/details/120335922
[1012 _python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120336993
[1016 _python3]: https://blog.csdn.net/qq_39445165/article/details/120337862
[187 _python3 _ _ dfs]: https://blog.csdn.net/qq_39445165/article/details/120351436
[272 _python3]: https://blog.csdn.net/qq_39445165/article/details/120368117
[1275 _c_-java]: https://blog.csdn.net/qq_39445165/article/details/119853927
[245 _c_-java]: https://blog.csdn.net/qq_39445165/article/details/119864286
[243 _2_c_-java]: https://blog.csdn.net/qq_39445165/article/details/119945323
[1277 _c_-java]: https://blog.csdn.net/qq_39445165/article/details/119961694
[285 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120291458
[1072 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120519451
[1073 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120532909
[1074 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120555880
[323 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120562867
[1077 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120568723
[dp]: https://blog.csdn.net/qq_39445165/article/details/120471785
[282 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120469327
[1068 _python3]: https://blog.csdn.net/qq_39445165/article/details/120472821
[320 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120477409
[1069 _python3 _dp _]: https://blog.csdn.net/qq_39445165/article/details/120494181
[479 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120497781
[321 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120513555
[dp_python3]: https://blog.csdn.net/qq_39445165/article/details/120572315
[Cxn_python3]: https://blog.csdn.net/qq_39445165/article/details/116422097
[1081 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120575281
[1082 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120578154
[1083 Windy_python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120579239
[1084 _ II_python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120589222
[1085 _62_python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120592926
[1086 _7_c_-python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120605206
[1088 _python3]: https://blog.csdn.net/qq_39445165/article/details/120624444
[256 _Trie]: https://blog.csdn.net/qq_39445165/article/details/119977394
[423 _python3]: https://blog.csdn.net/qq_39445165/article/details/120188642
[1024 _python3]: https://blog.csdn.net/qq_39445165/article/details/120189166
[3 _python3]: https://blog.csdn.net/qq_39445165/article/details/120237492
[python3]: https://blog.csdn.net/qq_39445165/article/details/118597543
[1022 _python3]: https://blog.csdn.net/qq_39445165/article/details/120194113
[278 _python3]: https://blog.csdn.net/qq_39445165/article/details/120209461
[4 _ I_python3]: https://blog.csdn.net/qq_39445165/article/details/120211348
[1019 _python3]: https://blog.csdn.net/qq_39445165/article/details/120211706
[1023 _python3]: https://blog.csdn.net/qq_39445165/article/details/120229358
[Link 2]: https://blog.csdn.net/qq_39445165/article/details/120233950
[1020 _python3]: https://blog.csdn.net/qq_39445165/article/details/120234426
[12 _python3]: https://blog.csdn.net/qq_39445165/article/details/120239903
[9 _python3]: https://blog.csdn.net/qq_39445165/article/details/120241400
[1013 _python3]: https://blog.csdn.net/qq_39445165/article/details/120244085
[487 _c_-python3]: https://blog.csdn.net/qq_39445165/article/details/120251920
[426 _python3]: https://blog.csdn.net/qq_39445165/article/details/120253342
[1021 _python3]: https://blog.csdn.net/qq_39445165/article/details/120257016
[532 _python3]: https://blog.csdn.net/qq_39445165/article/details/120267203
[5 _ II_python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120272536
[7 _python3]: https://blog.csdn.net/qq_39445165/article/details/120274923
[10 _c_-python3 _ _ _dp]: https://blog.csdn.net/qq_39445165/article/details/120304315
[11 _python3]: https://blog.csdn.net/qq_39445165/article/details/120309730
[734 _python3 _ _]: https://blog.csdn.net/qq_39445165/article/details/120318802
[301 _2_python3]: https://blog.csdn.net/qq_39445165/article/details/120688802
[302 _3_python3]: https://blog.csdn.net/qq_39445165/article/details/120710372
[dp 1]: https://blog.csdn.net/qq_39445165/article/details/120411290
[291 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120402452
[1064 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120415583
[327 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120422971
[292 _python3 _dp]: https://blog.csdn.net/qq_39445165/article/details/120439601
[524 _python3 _dp-_dp]: https://blog.csdn.net/qq_39445165/article/details/120463882
[1049 _python3]: https://blog.csdn.net/qq_39445165/article/details/120372154
[1057 _ IV_python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120381335
[1058 _ V_python3]: https://blog.csdn.net/qq_39445165/article/details/120382485
[1052 _python3 kmp _]: https://blog.csdn.net/qq_39445165/article/details/120385823
[Link 3]: https://blog.csdn.net/qq_39445165/article/details/120625154
[135 _python3]: https://blog.csdn.net/qq_39445165/article/details/120609010
[1089 _python3]: https://blog.csdn.net/qq_39445165/article/details/120626796
[1090 _python3 _ _]: https://blog.csdn.net/qq_39445165/article/details/120629286
[1087 _python3]: https://blog.csdn.net/qq_39445165/article/details/120636582
[1091 _python3]: https://blog.csdn.net/qq_39445165/article/details/120639306
[Link 4]: https://blog.csdn.net/qq_39445165/article/details/120726310
[python]: https://blog.csdn.net/qq_39445165/article/details/120518686
[python 1]: https://blog.csdn.net/qq_39445165/article/details/120836669
[849 Dijkstra_ I_python3 _Dijkstra]: https://blog.csdn.net/qq_39445165/article/details/120728336
[850 Dijkstra_ II_python3 _Dijkstra]: https://blog.csdn.net/qq_39445165/article/details/120732729
[851 spfa_python3 spfa]: https://blog.csdn.net/qq_39445165/article/details/120743101
[1129 _python3]: https://blog.csdn.net/qq_39445165/article/details/120746090
[1128 _python3 floyd]: https://blog.csdn.net/qq_39445165/article/details/120747683
[1127 _python3 spfa]: https://blog.csdn.net/qq_39445165/article/details/120751983
[1126 _python3]: https://blog.csdn.net/qq_39445165/article/details/120754530
[920 _python3 _--]: https://blog.csdn.net/qq_39445165/article/details/120767607
[903 _python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120774159
[1135 _python3 _ _ dfs]: https://blog.csdn.net/qq_39445165/article/details/120798388
[340 _python3 _ _]: https://blog.csdn.net/qq_39445165/article/details/120803736
[342 _python3 _ _]: https://blog.csdn.net/qq_39445165/article/details/120809206
[341 _python3 _ _ dp]: https://blog.csdn.net/qq_39445165/article/details/120817591
[1131 _python3 _-_dp]: https://blog.csdn.net/qq_39445165/article/details/120871287
[1134 _python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120885947
[383 _python3 _-]: https://blog.csdn.net/qq_39445165/article/details/120894279
[Link 5]: https://blog.csdn.net/qq_39445165/article/details/120895084
[1125 _python3 floyd]: https://blog.csdn.net/qq_39445165/article/details/120927307
[343 _python3 floyd]: https://blog.csdn.net/qq_39445165/article/details/120939903
[344 _python3 floyd]: https://blog.csdn.net/qq_39445165/article/details/120982059