题目链接:洛谷 P1048 题目大意 给定一个最大重量为 $V$ 的背包,和 $n$ 个物品。每个物品有一个重量和价值。现在问在背包可以装下的范围内,最大的价值是多少。 朴素 DP 我们定义 dp[i][j] 为到第 $i$ 个物品,背包的重量为 $j$ 的最大价值。 我们可以得出状态转移方程: $$ \text{dp[i][j] = max(dp…
介绍了 Tarjan 求割点和桥。
模意义下的乘法逆元
树状数组学习笔记。
拓扑排序的介绍。
并查集学习笔记。
快速幂是一种基于二分思想运算幂的算法。
ST 表 ST 表运用了倍增的思想。 其中 $dp_{i, j} = \max(i \to i + 2^j - 1)$,也就是 $dp_{i, j}$ 的值是区间 $[i, i + 2^j - 1]$ 中的最大值。 通过上面的定义,显然 $dp_{i,0} = \max(i \to i + 2^0 - 1) = \max(i \to i) = a_…
欧拉回路和欧拉路径的总结
BFS、DFS 和图的储存与最短路算法。