DP的状压优化

状态压缩

作为OIers，我们不同程度地知道各式各样的算法。
大部分问题的算法都有一个多项式级别的时间复杂度上界（如O(log n)），我们一般称这类问题为P类(deterministic Polynomial-time)问题，例如在有向图中求最短路径。
然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法，对这些问题尚不知有多项式时间的算法存在。
对于某些至今尚未找到多项式时间复杂度的算法，然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。毫无疑问，对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞赛那有限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP问题，暴力搜索的复杂度是O(n!)，如此高的复杂度使得它对于高于10的数据规模就无能为力了。那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表现比搜索好呢？答案是肯定的——

动态规划

大航海 >>

从前向星到链式前向星

我们首先来看一下什么是前向星.

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

存储

大航海 >>

SPFA(SuPerFrAnky)

这篇讲的还是很(比较)清楚的吧~

适用范围：

给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。
我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。

算法

大航海 >>

关于二分的边界问题的大讨论

二分区间可以是左闭右开，或者都闭也行。
如果是都闭，判断条件是while(L<R)。如果是L+1，那么就需要mid=L+(R-L)/2，靠近L一点。如果是R-1，就注意要mid=L+(R-L+1)/2，靠近R一点。这样做是为了避免出现区间[a,a+1]出现死循环问题。
总之二分的条件很灵活，判断条件也可以是L<R-1，L和R也可以都等于mid，还是要看情况，只要避免死循环就行了。

二分

大航海 >>

ST算法

作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例

举例：

给出一数组A[0~5] = {5,4,6,10,1,12},则区间[2,5]之间的最值为1。

方法：ST算法分成两部分：离线预处理 （nlogn）和 在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。

（1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。

（2）在线查询：对给定区间进行分割，借助该二维数组求最值

算法

大航海 >>

,