- ACM Note No.14: Liner DPACM-ICPC
动态规划（Dynamic Programming, DP），动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。使用动态规划需要满足三个条件：最优子结构，无后效性和子问题重叠。 最优子结构：一…
- ACM Note No.15: Knapsack DPACM-ICPC
背包DP分为01背包、完全背包、多重背包等等 背包容量有限，在 n 个物品中拿若干个，如何使得拿到的物品价值最大 因为一个物品只有拿或者不拿两种选择，因此称为01背包 状态定义：dp[i][j]表示在只考虑前i个物品的情…
- ACM Note No.10: DSUACM-ICPC
并查集（DSU， Disjoint Set Union），顾名思义是一种能高效合并两个集合并查询某个数属于哪一个集合的数据结构，在处理连通分量（连通块）问题方面应用十分广泛 并查集实现的为一个森林，其核心思想有二： 将每…
- ACM Note No.11: MSTACM-ICPC
最小生成树（Minimum Spanning Tree，MST），是一个有权图删除若干边能得到的边权和最小的树 常见的求最小生成树的算法有 Prim 算法 和 Kruskal 算法 从小到大加入边，直到所有的点连通 <img…
- ACM Note No.12: DijkstraACM-ICPC
Dijkstra 算法可用于求解非负权图上的单源最短路径，在非负权图上对单个点跑一遍 Dijkstra 就可以知道该点到其他所有点的最短路径 Dijkstra 算法的核心思想是贪心： 如果 A -> C 的路程为 A -…
- ACM Note No.13: FloydACM-ICPC
Floyd 算法可用于求解非负权图上的多源最短路径，在非负权图跑一遍 Floyd 就可以知道该所有点到其他所有点的最短路径 Floyd 算法的核心思想是动态规划： i节点到j节点的最短路径取决于 [i节点经过k节点到达j…
- ACM Note No.9: GraphACM-ICPC
图的存储方式有主要的两种：邻接表与邻接矩阵 邻接表：使用vector<vector<node>>存储，存储节点i的所有出边和权值 邻接矩阵：使用二维数组存储，mp[i][j] = w表示节点i到j有一条权值为w的边 给定…
- ACM Note No.6: DFSACM-ICPC
深度优先搜索（DFS）常常用于解决图的连通性问题，暴力枚举问题等等 DFS常常用递归实现： 从1∼n 这 n个整数中随机选出 m个，输出所有可能的选择方案。 #include <bits/stdc++.h> using…
