最长上升子序列

1、最长上升子序列(easy)：给定一个长度为 $n$ 的数组 $a$ ($n \leq 1000$)，求其最长上升子序列(非降)的长度。注意：子序列不一定是连续的
2、对于线性 DP，通常用 $dp[i]$ 表示以 $i$ 结尾或到 $i$ 为止，如果有对应的代价，通常用 $dp[i][j]$ 表示到 $i$ 为止花费 $j$ 的代价的价值最值(见背包问题)
3、确定状态：令 $dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度
4、确定转移：对于输入的每一个 $a[i]$ ，可知都有两种情况：一种是它作为最长上升子序列的起点，另一种是它接续在其他上升子序列之后。对于 $a[i]$ 作为起点，$dp[i] = 1$ ；对于 $a[i]$ 作为接续，应向左搜寻一个 $j \lt i$，$dp[i] = max(dp[i], dp[j] + 1)$ ，遍历取最大值。总结状态转移方程为：
$$ \left\{ \begin{array}{l} dp[i] = 1 &作为起点 \\\\ dp[i] = max(dp[i], dp[j] + 1) &作为接续 \\\end{array} \right. $$
5、易知，该算法复杂度为 $O(n^2)$，只能处理小规模数据，仍需优化

采药

1、采药：输入 $T$ 和 $M$ 分别表示拥有的总时间和药材种类($T \leq 1000, M \leq 100$)，对于每种药材，输入 $t_i$ 和 $v_i$ ($t_i,v_i \leq 100$)，表示采摘该药材需要的时间和药材的价值，每种药材只可采摘一次。可能输入多组数据，直到 $T$ 和 $M$ 都为 $0$ 结束。对于每组数据，输出其规定时间内能采摘的药材价值之和的最大值
2、对于每种药材都可以用 $0$ 或 $1$ 标记状态(是否被选择)，是一个01 背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的时间，所获得的最大价值
3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费时间，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j-t[i]] + v[i]$(当前状态等同于 $dp[i-1][j-t[i]]$ 上一个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总时间为 $j$，所以上一个物品的时间应为 $j-t[i]$)。总结状态转移方程为：
$$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i-1][j-t[i]] + v[i]&,选择了当前物品 \\ \end{array} \right. $$
4、最后确定初始化和边界：初始化 $dp[0][i] = 0$(到第 $0$ 个物品无论花费多少时间，价值为 $0$)；边界为 $i \leq M, j \leq T$

递推求组合数

1、组合数中有 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。其中 $C_n^m$ 意为从 $n$ 个元素中选出 $m$ 个元素有多少种不同组合，其总的可能可划分为组合中选了第一个和组合中没选第一个两种。如果组合中选了第一个，那么剩下的方案数还有 $C_{n-1}^{m-1}$ 种(从剩余元素中选 $m-1$ 个)；如果组合中没选第一个，那么剩下的组合中还有 $C_{n-1}^m$ 种；这两种结果互斥，因此相加便可得到总的方案
2、这种方法运用了递推与DP的思想，上面的等式为状态转移方程。其中，$C_n^m$ 为新状态，通过方程将其转移为两个老状态的和。此外，需要确定起始点和边界：起始点为 $C_i^0 = 1$ (从任意多的元素中选 $0$ 个，有 $1$ 种方案——不选)；边界为 $C_i^j$ (其中 $0 \leq j \leq i$，$i \leq n$)

生成树 与 MST

1、在无向连通图中，找出一个节点最多的子连通图(有 $n$ 个点，$n-1$ 条边)，这样的子连通图一定是树，称为生成树。最小生成树指各边权值之和最小的生成树，称为 MST(Minimum Spanning Tree)
2、如下图，便是一幅无向连通图，该图的最小生成树为图中红色所示的子连通图(有 $5$ 个点，$4$ 条边)，其权值和为 $10$
3、对于最小生成树的生成，可以通过基于点的 Prim 最小生成树与基于边的 Kruskal 最小生成树完成

Dijkstra 朴素算法

1、最短路 1：给定 $n$ 个点 $m$ 条边的有向图($n \leq 1000$)，输出点 $1$ 到 $n$ 的最短距离。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边。如果不存在路径，输出 $-1$
2、先前在图与回溯中介绍过权值相等最短路(无权最短路)，现在有了权值，需要做一个结构体保存。Dijkstra还使用一个数组 $d[]$ ，$d[i]$ 表示从起点 $st$ 到 $i$ 的最短距离
3、Dijkstra 思路如下图：起始时，建图，标记所有 $d[i]$ 为 $\infty$，以 $1$ 为起点，向外走一层，将经过的边松弛(用边的权值更新所到点的 $d[i]$ ，$d[i]$ 取较小值)；接下来，比较得到最小的 $d[i]$ ，以该点为当前起点(图中为点 $2$)，先前的点已经可以忽略，继续向外走一层，将经过的边松弛(注意，$d[3]$ 取较小值更新为 $3$)；以此类推，以 $4$ 为当前起点发现点 $4$ 没有出点，返回；以 $3$ 为当前起点，走到终点，更新 $d[5]$ 为 $6$，所以最短路为 $6$
4、该算法结合了贪心和DP的思想，每个点只拓展一次，且拓展时已为最短距离

并查集

1、并查集是一种支持合并和查询操作的集合形式的数据结构，它支持两个集合的合并，并可以查询点与点之间的连通关系
2、并查集只需要一个数组 $pre[]$ 存储点的前导点(父节点)，在初始化时 $pre[i] = i$ ，表示点与自己连通，是单独的连通块，该功能由 $init()$ 函数完成。并查集中还需要一个函数 $root(u)$ ，该操作将找到点 $u$ 所属的连通块(的根节点)。该函数将递归查找 $u$ 的父节点，直至找到根节点
3、对于两个点 $u$ 和 $v$ 的合并操作，只需要将 $u$ 和 $v$ 所属的连通块的其中一个根指向另一个根即可，如 $pre[root(u)] = root(v)$ ；对于两个点 $u$ 和 $v$ 的查询操作，只需要判断 $u$ 和 $v$ 所属的连通块的根是否相同即可
4、但前述 $root(u)$ 函数的朴素算法每次都需要查找一整条父节点，效率太低，可以通过路径压缩优化程序： $pre[u] = (pre[u] == u ? u : root(pre[u]))$ ，这样同一连通块在第一次查找后，每个节点都将直接指向当前根节点，提高以后查找的效率

树状数组

1、树状数组常用于维护区间和，有以下操作：单点修改 $O(\log n)$，区间修改 $O(\log n)$，区间查询 $O(\log n)$
2、树状数组的结构如下图，注意树状数组中一定不能用下标 $0$ 。$T[i]$ 所存的值为管辖区间的和，$T[i]$ 所覆盖的管辖区间为 $[i - lowbit(i) + 1, i]$ ，管辖区间长度为 $lowbit(i)$
3、$lowbit(i)$ 表示 $i$ 的二进制只保留最后一位 $1$ 的结果(例如二进制 $1101100$ 只保留后三位变为 $100$)，公式为 $lowbit(x) = x \land -x$

单调栈

1、在栈的基础上，如果保持栈内元素是有序的，则称为单调栈，分为单调递增栈和单调递减栈
2、通常单调栈主要用于求位置最近的更大值或更小值，我们将在具体样例中分析