这里更新主要更新一些 模板 / 数据结构 /… 的题目吧

# 图

# 并查集

【定义】：用来管理元素分组情况的数据结构。并查集可以高效的进行如下操作：

  • 查询元素 a 和元素 b 是否属于同一组
  • 合并元素 a 和 b 所在的组
    需要注意并查集只能进行合并操作，但是无法进行分割操作
    【结构】：并查集是利用树形结构实现的。不过不是二叉树。
    （1）初始化：
    首先准备 n 个节点代表 n 个元素。最开始没有边。
    初始化
    （2）合并：
    如图，从一个组的根向另一个组的根连边，这样两棵树变成一颗树，也就把两个组合合并为一个组。
    合并
    （3）查询：
    为了查询两个节点是否属于同一组，需要沿着树向上走，来查询包含这个元素的根是谁。两个节点走到同一个根，则说明他们属于同一组。下图 5，2 走到 1，7 走到 6，所以 7 和 2，5 不是同一组。
    查询
    并查集实现中注意的点：
    避免退化！
  • 对于每颗树，记录这棵树的高度（rank）
  • 合并时如果两棵树的 rank 不同，则 rank 小的向 rank 大的连边。
    此外，通过路径压缩，可以使并查集更高效。对每个节点，一旦走到了一次根节点，就把这个点到父亲的边改为直连连向根。如图
    路径压缩

这里给出并查集的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int par[MAX_N]; //父亲
int rank[MAX_N]; //树的高度

// 初始化n个元素
void init(int n){
	for(int i = 0; i < n; i++){
		par[i] = i;
		rank[i] = 0;
	}
}

//查询树的根
int find(int x){
	if(par[x] == x){
		return x;
	} else {
		return par[x] = find(par[x]); //路径压缩
	}
}

// 合并x和y所属的集合
void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rank[x] < rank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if (rank[x] == rank[y]) rank[x]++;
	}
}
// 判断 x 和 y 是否属于同一个集合
bool same(int x, int y){
	return find(x) == find(y);
}

# 并查集题目扩展思路

这里遇到了一个很有意思的题，类型是：类似于倒着的并查集连接，当一个图失去了某个顶点，求当前图是否连通，或者当前图有几个联通分量。思路是记录各边，倒着以并查集合并的方式做题。
P3144 [USACO16OPEN] Closing the Farm S
P1197 [JSOI2008] 星球大战 这道题有一个很好的数据结构，链式前向星来表示边，这样可以查看特定的与某个相连的顶点的所有边

# 拓扑排序

有向无环图
如果有一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图（DAG）。
拓扑排序是指将有向无环图 G 的所有顶点排成一个线性序列，使得对图 G 中任意两个顶点 u,v，如果存在边 u->v，那么在序列中 u 一定在 v 前面。这个序列称为拓扑序列。我们可以以课程的学习先后顺序为例，例如图中所示，每门课程有其先导课程，必须先学习好其先导课程才能很好的学习这门课，并且先导课程之间不能形成环。在有了课程的联系信息之后，我们可以将课程排列成一个学习的先后序列，使得其满足先导课程顺序，这便是拓扑排序。
下面介绍拓扑排序的抽象步骤:

  • ①定义一个队列 Q，并把所有入度为 0 的节点加入队列。
  • ②取队首系欸但，输出。然后删除所有从它出发的边，并令这些边到达的顶点的入度减 1，如果某个顶点的入度减为 0，则将其加入队列。
  • ③反复进行②，直到队列为空。如果队列为空时入队的节点数目恰好为 N，则说明拓扑排序成功，图 G 为有向无环图；否则，排序失败，图 G 中有环。
    可以使用邻接表实现拓扑排序，但是由于需要记录节点的入度，需要额外建立一个数组 inDegree [MAX_V] 来存储入度。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> G[MAX_V]; //
int n,m,inDegree[MAX_V];
bool topologicalSort(){
	int num = 0;
	queue<int> q;
	for(int i = 0; i< n ;i++){
		if(inDegree[i] == 0) q.push(i);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0;i < G[u].size(); i++){
			int v = G[u][i];   //u的后继节点v
			inDegree[v]--;
			if(inDegree[v] == 0){
				q.push(v);
			}
		}
		G[u].clear();
		num++;
	}
	if(num == n) return true;
	else return false;
}

其用来进行判断一个给定的图是否是有向无环图。最后指出：如果题目有要求当有多个入度为 0 的顶点时选择编号最小的顶点，那么将 qu
eue 改为 priority_queue，保证队首元素最小编号即可。

# 关键路径

# AOV 网和 AOE 网

顶点活动网（AOV）是指用顶点表示活动，而用边集表示活动间优先关系的有向图。显然，图中不应该出现有向环，否则会让优先关系出现逻辑错误。
边活动 (AOE) 网是指用带权的边集表示活动，而用顶点表示事件的有向图，其中边权表示完成活动需要的时间。
一般来说，AOE 网可以用来表示一个工程的进行过程，而工程常常可以分为若干个子工程，显然 AOE 网不应该出现环。考虑到对工程来说有一个起始时刻和结束时刻，因此 AOV 网一般只有一个源点和一个汇点。虽然这么说，即使有多个源点和汇点，也可以转换为一个源点和汇点的情况（即添加一个超级源点和超级汇点连接所有源点和汇点）。
既然 AOE 网是基于工程提出的概念，那么一定有其需要解决的问题。AOE 网需要着重解决两个问题：a. 工程起始到终止至少需要多少时间；b. 那条路径上的活动是影响整个工程进度的关键。AOE 网中最长的路径被称为关键路径，而把关键路径上的活动称为关键活动。

# 最小生成树

再来复习一下最小生成树吧 ：）
【生成树定义】给定一个无向图，如果它的某一个子图中任意两个顶点都相互连通并且是一棵树，那莪这棵树就叫做生成树。如果边上有权值，那么使得边权和最小的生成树是最小生成树。
【应用例题】：
例题示例

# 算法 1（Prim 算法）

首先，我们假设有一颗只包含一个点 v 的树 T。然后贪心选取 T 和其他顶点之间相连的最小权值的边，并把它加到 T 中。不断进行这个操作，即可获得一个生成树。下面来证明：
我们令 V 表示顶的集合。假设现在已经求得的生成树的顶点的集合是 X（⊂\subset V）, 并且存在在 V 上的最小生成树使得 T 是它的一个子图。下面我们证明存在一棵最小生成树使得 T 是它的一个子图并且它包含了连接 X 和 V\X 的权值最小的边。记连接 X 和 V\X 的权值最小的边为 e，它连接着 V（∈X）和 u (∈V \ X)。 根据假设，存在一颗 V 上的最小生成树使得 T 是它的一个子图。如果 e 也在这棵最小生成树上，问题就得到证明了，所以我们假设 e 不再这棵书上。因为生成树的本质是一棵树，所以在添加了 e 之后就形成了圈。
算了，抄别人的证明太难受了，我说一下自己的想法吧，虽然可能很潦草还有错误但是能理解就行：就是一个无向图，那我们随机取一个点，找这个点所能连的最小的边（为什么能随机取，因为任意一个点所连的最小边一定要取，满足贪心），如果选的最小边会使生成树产生环，则取次小边，直到所有点都被取到。
那直接根据我的定义上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int cost[MAX_V][MAX_V]; //表示 e=(u,v)的权值，不存在的情况下为INF
int mincost[MAX_V];     //从集合X 出发的边到每个顶点的最小权值
bool used[MAX_V];       //顶点i是否被包含在集合X中
int V; //顶点数

int prim(){
	for(int i = 0;i < V; i++){
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;  //由于随机取都行 这里直接拿第一个
	int res = 0;
	while(true){
		int v = -1; //从不属于X的顶点选取从x到其权值最小的顶点
		for(int u = 0; u < V; u++){
			if(!used[u]&&(v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if(v == -1) break;
		used[v] = true;
		res += mincost[v];
		for(int u = 0;u <V; u++){
			mincost[u] = min(mincost[u], cost[v][u]);  //更新集合X 出发到每个边的最小权值
		}
	}
	return res;
}

# 算法 2（Kruskal 算法）

下面是 Kruskal 算法。其是按照边的权值进行排序从小到大，如果不产生圈，就加上这条边。主要就是如何判断加的边是否形成圈（这里似乎可以用并查集的方法–> 如果两个要连接的点属于同一根 则会形成圈 不属于同一根 则可以链接） Kruskal 在边排序较为费时间（边太多可以用 Prim 算法）
下面上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct edge{int u,v,cost;};
int par[MAX_V],rank[MAX_V];

void init_union_find(int x){
	for(int i=0;i<V;i++){
		par[i] = i;
		rank[i] = 0;
		}	
}

int find(int x){
	if(par[x] == x) return x;
	else{
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rank[x] < rank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if (rank[x] == rank[y]) rank[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y) ;
}

bool cmp(const edge& e1,const edge& e2){
	return e1.cost < e2.cost;
}
edge es[MAX_E];
int V,E; //V 定点数 E 边数

int Kruskal(){
	sort( es, es+ E, cmp);
	init_union_find(V);
	int res = 0;
	for(int i = 0;i < E; i++){
		edge e = es[i];
		if(!same(e.u,e.v)){
			res += e.cost;
			unite(e.u,e.v);
		}
	}
	return res;
}

# 堆

【定义】 堆是一棵完全二叉树，树种每个结点的值都不小于（或不大于）其左右孩子结点的值。堆其实可以用 STL 库中的优先队列 (priority_queue) 代替。这里给出堆的手打模板。数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int heap[MAX_N],sz=0;
void push(int x){
	int i =sz++;    //自己的节点编号
	while(i > 0){
		int p = (i-1) / 2;   //父亲的节点编号
		if(heap[p] <= x) break;   //如果没有大小颠倒 退出
		heap[i] = heap[p];     //把父亲节点的数值放下去，把自己提上去
		i = p;
	}
	heap[i] = x;
}
int pop(){
	int ret = heap[0];   //最小值
	int x = heap[sz--];  //要提到根的数值
	int i = 0; //从根开始向下交换
	while(i * 2 + 1 <sz){
		//比较儿子的值
		int a = i * 2 + 1, b = i * 2 + 2;
		if(b < sz && heap[b] < heap[a]) a=b;
		//如果已经没有大小颠倒则退出
		if(heap[a] >= x) break;
		//把儿子的数值提上取去
		heap[i] = heap[a];
		i = a;
	}
	heap[i] = x;
	return ret;
}

# 最短路径算法

最短路径是图论中一个很经典的问题：给定图 G (V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边权和最小。即对任意给出的图 G (V,E) 和起点 S，终点 T，求 S 到 T 的最短路径。 常用的有 Dijkstra 算法，Bellman-Ford 算法，SPFA 算法，Floyd 算法。

# Dijkstra 算法

其可以用来求解单源最短路问题，即给定图 G 和起点 s，可以得到 S 到达每个顶点的最短距离。Dijkstra 的基本思想是对图 G (V,E) 设置集合 S，存放已被访问的顶点，然后每次从集合 V-S 中选择与起点 s 的最短距离最小的一个顶点（记为 u），访问并加入集合 S。之后，令顶点 u 为中介点，优化从 s 与所有从 u 能到达的顶点 v 之间的最短距离。这样的操作执行 n 次，（n 为顶点个数）直到集合 S 已经包含所有的顶点。
其算法策略是：
①每次从集合 V-S (未到达的节点) 中选择与起点 s 最短距离最小的顶点 u，访问并加入 S。
②之后，令顶点 u 为中介点，优化起点 s 和所有从 u 能到达的顶点 v 之间的最短距离。
下面给出伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
//G为图，一般设成全局变量；数组d为源点到达各个点的最短路径长度，s为起点
Dijkstra (G,d[],s){
	初始化
	for(循环n){
		u = 使d[u]最小的还未被访问的顶点的编号
		for(从u出发能到达的所有顶点v){
			if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优){
				优化d[v];
			}
		}
	}
}

这里只实现邻接表版本的，邻接矩阵内核都是与上述伪代码一样。算了还是写临界矩阵的把
邻接矩阵版本：(这里加上了前驱节点可以获得最短路径)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n,G[MAX_V][MAX_V];  //n为顶点数，MAX_V为最大顶点数
int d[MAX_V]; //起点到达各个点的最短路径长度
int pre[MAX_V];  //pre[v] 表示从起点到顶点v的最短路径上v的前一个顶点
bool vis[MAX_V] = {false};

void Dijkstra(int s){
	fill(d, d+MAX_V, INF);
	d[s] = 0;  //起点s到自身的距离是0
	for(int i = 0; i< n;i++){
		int u = -1,MIN = INF;   //u使d[u]最小，MIN存放该最小的d[u]
		for(int j = 0; j < n; j++){   // 找到未被访问的顶点d[]中最小的
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		//找不到小于INF 的 d[u],说明剩下的顶点和起点s不连通
		if( u == -1) return;
		vis[u] = true;
		for(int v = 0; v< n; v++){//如果v未访问&& u能到达v &&以u为中介点可以使d[v]更优
			if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
				d[v] = d[u] + G[u][v];
				pre[v] = u;
			}
		}
	}
}

void DFS(int s, int v){
	if(v == s){
		printf("%d\n",s);
		return;
	}
	DFS(s,pre[v]);
	printf("%d\n",v);
}

邻接表版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//邻接表版本
struct Node{
	int v,dis;   //v为边的目标顶点，dis为边权
}
vector<Node> Adj[MAX_V];  //图G，存放从顶点u触发可以到达的所有顶点
int n;//n为定点数
int d[MAX_V];//起点到达各个点的最短路径长度
bool vis[MAXV] = {false};  //标记数组，true表示已经被访问过

void Dijkstra(int s){
	fill(d,d+MAX_V,INF);   //fill函数讲d数组赋值为INF （慎用memset)
	d[s] = 0;
	for(int i= 0; i < n; i++){
		int u = -1, MIN = INF;
		for(int j = 0; j< n; j++){
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		//找不到小于INF的d[u],说明剩下的顶点和起点s不连通
		if(u == -1) return;
		vis[u] = true;
		for(int j = 0;j < Adj[u].size(); j++){
			int v = Adj[u][j].v;
			if(vis[v] == false && d[u] + Adj[u][j].dis < d[v]){
				d[v] = d[u] + Adj[u][j].dis; //优化d[v]
			}
		}
	}
}

如果是双向边，只需要添加两次邻接表即可。

# Dijkstra 扩展

先鸽一下

这里做了一道洛谷上的 P1629 邮递员送信 这道题有个很好的思路，对于起点到多个点的最短路径，如果求多个点到起点的最短路径，可以 Dijkstra 但是反向建图求 Dij。我觉得这个思路特别好。另外本题似乎要判断重边取最小，否则直接爆零。太惨了

扩展 2，洛谷的 P6833 雷雨 -, 这个题也是可以用 Dij 做，这里有一个很好的思路，但是感觉适应这个思路的地方比较少，具体可以点进去看之前的代码。

# Bellman-Ford 算法和 SPFA 算法

Dijkstra 算法可以很好解决无负权图的最短路径问题，但是如果出现了负权边，Dijkstra 算法就会失效。
Bellman-Ford 算法和 Dijkstra 算法一样，是用来求解单源最短路径问题，但是也能处理带有负权边的情况。现在考虑环，也就是从某个顶点出发，经过若干个不同顶点回到该顶点的情况。而根据环中边的边权之和的正负，可以将环分为零环，正环，负环。显然，零环和正环不会影响最短路径的求解，如果出现负环，且从源点可以到达，那么就会影响最短路径的求解。
与 Dijkstra 算法相同，Bellman-Ford 算法设置一个数组 d，用来存放源点到达各个顶点的最短距离。同时 Bellman-Ford 算法返回一个 bool 值：如果其中存在从源点可以到达的负环，那么函数将会返回 false，否则，函数将返回 true，此时数组当中存放的就是从源点到达各个顶点的最短路径。
Bellman-Ford 算法的主要思路如下面的伪代码所示。需要对图中的边进行 V-1 轮操作，每轮都遍历图中的所有边：对每条边 u->v，如果以 u 为中介点可以使 d [v] 更小，即 d [u]+length [u0>v] < d [v] 成立时，就用 d [u]+length [u->v] 更新 d [v]。

1
2
3
4
5
6
7
for(int i =0; i < n; i++){    //执行n-1轮操作，
	for(each edge u->v){   //每轮操作都遍历所有边
		if(d[u] + length[u->v] < d[v]){  //以u为中介点可以使d[v]更小
			d[v] = d[u] + length[u->v];  //松弛操作
		}
	}
}

此时，如果图中没有从源点可以到达的负环，那么数组 d 中的所有值已经到达最优。因此，只需要对所有的边进行一轮操作，判读是否某条边 u->v 仍然满足 d [u] + length [u->v] < d [v]，如果有，则说明图中有从源点可达的负环，返回 false，否则，说明数组 d 中所有值都达到最优，返回 true。

1
2
3
4
5
6
for(each edge u->v){   //对每条边进行判断
	if(d[u] + length[u->v] < d[v]){   //如果仍可以被松弛
		return false;   //说明图中有从源点可达的负环
	}
}
return true;  //数组d的所有值已经达到最优

这里给出临界表的方法，由于 Bellman-Ford 需要遍历所有的边，故邻接矩阵使用时可能会导致复杂度上升的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Node{
	int v,dis;  //v是邻接表的目标顶点，dis为邻接边的边权
}
vector<Node> Adj[MAX_V];   //G的邻接表
int n;   //n为定点数
int d[MAX_V];   //起点到达各个点的最短路径长度

bool Bellman(int s){
	fill(d, d+ MAX_V, INF);
	d[s] = 0;
	for(int i= 0; i<n-1 ; i++){   //进行n - 1 轮操作
		for(int u = 0;u < n ;u++){    //每轮操作都遍历所有边
			for(int j = 0;j < Adj[u].size(); j++){
				int v =Adj[u][j].v;  //邻接边的顶点
				int dis = Adj[u][j].dis;  // 邻接边的边权
				if(d[u] + dis < d[v]){  //以u为中介点可以使d[v]更小
					d[v] = d[u] + dis; //松弛操作
				} 
			}
		}
	}
	//下面是判断负环的代码
	for(int u = 0 ;u < n; u++){
		for(int j = 0; j < Adj[u].size(); j++){
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;
			if(d[u] + dis < d[v]){
				return false;
			}
		}
	}
	return true;
}

虽然 Bellman-Ford 算法的思路很简洁，但是由于其 O (VE) 的时间复杂度确实较高，在很多情况下并不尽人意。其实，BF 算法的每轮操作都需要操作所有边的话，显然其中会有重复的无意义操作，严重影响了算法的性能。只有当某个 1 顶点 u、的 d [u] 的值改变时，从它出发的边的邻接点 v 的 d [v] 值才有可能被改变。 由此可以进行一个优化： 建立一个队列，每次将队列队首顶点 u 去除，然后对从 u 出发的所有边 u->v 进行松弛操作，也就是判断 d [u] + length [u->v] < d [v] 是否成立，如果成立，则用 d [u] + length [u->v] 覆盖 d [v]，于是 d [v] 获得更优的值，如果 v 不再队列中，就把 b 加入队列。这样操作直到队列为空（说明图中没有从源点可达的负环），或者是某个顶点入队次数超过 V-1。下面是伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> Q;
源点s入队;
while(队列非空){
	取出队首元素u;
	for(u的所有邻接边u->v){
		if(d[u] + dis < d[v]){
			d[v] = d[u] + dis;
			if(v当前不在队列){
				v入队;
				if(v入队次数大于n-1){
					说明有可达负环,return;
				}
			}
		}
	}
}

这种优化后的算法被称为 SPFA，它的期望时间复杂度是 O (KE)，E 是图的变数，K 是常数，在很多情况下 k 不超过 2. 但是如果图中有从源点可达的负环，则时间复杂度会退化程 O (VE。理解 SPFA 的关键是它如何从 Bellman-Ford 算法优化而来的。下面给出邻接表图的 SPFA 代码。注意：使用 SPFA 可以判断是否存在从源点可达的负环，如果负环从源点不可达，需要添加一个辅助顶点 C，并添加一条从源点到达 C 的有向边以及 V-1 条从 C 到达除源点外各顶点的有向边才能判断负环是否存在。因为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<Node> Adj[MAX_V];  //图G的邻接表
int n,d[MAXV],num[MAXV];  //num表示顶点入队次数
bool inq[MAXV];  //顶点是否在队列中

bool SPFA(int s){
	//初始化部分
	memset(inq,false,sizeof(inq));
	memset(num,0,sizeof(num));
	fill(d,d+MAXV,INF);
	queue<int> Q;
	Q.push(s);  //源点入队
	inq[s] = true; //源点已经入队
	num[s]++;  //源点入队次数加1
	d[s]=0;   //源点的d值为0
	//主体部分
	while(!Q.empty()){
		int u = Q.front(); //队首顶点编号为u
		Q.pop();  //出队
		inq[u] = false;  //设置u为不在队列中
		for(int j = 0; j<Adj[u].size();j++){
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;
			//松弛操作
			if(d[u] + dis < d[v]){
				d[v] = d[u] + dis;
				if(!inq[v]){  //如果v不再队列中
					Q.push(v);
					inq[v] = true;
					num[v]++;
					if(num[v] >= n) return false;
				}
			}
		}
	}
	return true;
}

# Floyd 算法

弗洛伊德算法可以用来解决全源最短路径问题，即对给定的图 G (V,E)，求任意两点 u，v 之间的最短路径长度，时间复杂度为 O (n3n^3)。由于其复杂度限制了定点数 n 在 200 以内，因此使用邻接矩阵来实现 Floyd 算法是非常合适和方便的。
Floyd 算法基于这样一事实：如果存在顶点 k，使得以 k 作为中介点时顶点 i 和顶点 j 的当前最短距离缩短，则使用顶点 k 作为顶点 i 和顶点 j 的中介点，即当 dis [i][k] + dis [k][j] < dis [i][j] 时，令 dis [i][j] = dis [i][k] + dis [k][j]。
基于上面的事实，Floyd 算法的流程非常简单，代码也很简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
\#include<cstdio>
\#include<algorithm>
using namespace std;
const int INF = 1000000000;
const int MAX_V = 200;  //MAX_V为最大顶点数
int n,m;   //n为顶点数，m为边数
int dis[MAX_V][MAX_V];  //dis[i][j]表示顶点i和顶点j的最短距离

void Floyd(){
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]){
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
}
/*
int main(){
 int u, v, w;
 fill(dis[0], dis[0] + MAX_V * MAX_V, INF);
 scanf()
}
*/

# 图论转化

这里介绍一些奇特的算法，即将一些常规问题转化为图论问题。

# 差分约束

差分约束系统是下面这种形式的多元一次不等式组。
![[Pasted image 20231219231448.png]]
（每个不等式称为一个约束条件，都是两个未知量之差小于或等于某个常数）
在算法竞赛中，很多题目会给出（或隐性地给出）一系列的不等关系，我们可以尝试把它们转化为差分约束系统来解决。
我们设 x1−x2<=cx_1 - x_2 <= c ，移项可得 x1<=x2+cx_1 <= x_2 + c
观察这个不等式与最短路问题中的三角形不等式dist[u]<=dist[u]+wv,udist[u] <= dist[u] + w_{v,u} 的相似之处。利用这一点，我们可以把它转化为一个图论问题。也就是说，对于每一个xci−xci′<=yix_{c_i} - x_{c_i'} <= y_i , 我们都从xci′x_{c_i'} 到xcix_{c_i} 建立一条边，权为yiy_i。
笔记来源： 算法学习笔记 (11): 差分约束

# 图论难点

# 强连通分量分解

【定义】对于一个有向图顶点的子集 S, 如果在 S 内任取两个顶点 u 和 v，都能找到一条从 u 到 v 的路径，那么就称 S 是强连通的。如果在强连通的顶点集合 S 中加入其他任意顶点集合后，它都不再是强连通的，那么就称 S 是原图的一个强连通分量。任意的有向图都可以分解成若干个不相交的强连通分量，这就是强连通分量分解。把分解后的强连通分量缩成一个顶点，就得到了一个 DAG（有向无环图）。

强连通分量的分解可以通过两次简单的 DFS 实现。
第一次 DFS 时，选取任意顶点作为起点，遍历所有尚未访问过的顶点，并在回溯前给顶点标号。对剩余的未访问过的顶点，不断重复上述过程。
完成标号后，越接近图的尾部（搜索树的叶子节点），顶点的标号越小。第二次 DFS 时，先将所有边反向，然后以标号最大的顶点为起点进行 DFS|。这样 DFS 所遍历的顶点集合就构成了一个强连通分量。之后，只要还有尚未访问的顶点，就从中选取标号最大的顶点不断重复上述过程。
(注：反向之后在当前节点能够访问到的顶点即是双向可达的，因此可通过这个连看哪些顶点是联通的)

将强连通分量缩点并得到 DAG。此时可以发现，标号最大的节点就属于 DAG 头部（搜索树的根）的强连通分量。因此，将边反向之后，就不能沿边访问到这个强连通分量以外的顶点。而对于强连通分量内的其他顶点，其可达性不受边反向的影响，因此在第二次 DFS 时，我们可以遍历一个强连通分量的所有顶点。
下面上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int V; // 定点数
vector<int> G[MAX_V];  //图的邻接边表示
vector<int> rG[MAX_V]; //把边反向后的表示
vector<int> vs;  //后序遍历顺序的定点列表
bool used[MAX_V];   //访问标记
int cmp[MAX_V]; //所属强连通分量的拓扑序
void add_edge(int from,int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}
void dfs(int v){
	used[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		if(!used[G[v][i]]) dfs(G[v][i]);
	}
	vs.push_back(v);
}
void rdfs(int v, int k){
	used[v] = true;
	cmp[v] = k;
	for(int i = 0;i < rG[v].size(); i++){
		if(!used[rG[v][i]]) rdfs(rG[v][i],k);
	}
}
int scc(){
	memset(used, 0,sizeof(used));
	vs.clear();
	for(int v = 0;v< V;v++){
		if(!used[v]) dfs(v);
	}
	memset(used, 0,sizeof(used));
	int k = 0;
	for(int i = vs.size() - 1; i>=0;i--){
		if(!used[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}

这里给出一个例题，

# 2-SAT

# Tarjan 算法 (强连通分量 / 缩点) 【还未完全理解】

首先，我们知道最基础的 DFS 算法对图进行搜索通过 vis 数组来判断是否访问某个节点，不过这里我们引入一个叫做时间戳的概念，代表每个节点第一次被访问的时间。如果我们用 tot 变量作为当前的时间，每访问一个节点 tot++。越先访问的节点的时间戳越小，越后访问的节点时间戳越大。在下面的代码中，我们用 dfn 数组作为每个点的时间戳，这样就可以取代 vis 数组。

1
2
3
4
5
6
7
8
int dfn[MAXN],tot = 0;
void dfs(int u){
	dfn[u] = ++tot;
	for(int e = first[u];e;e=nxt[e]){
		int v = go[e];
		if(!dfn[v]) dfs(v);
	}
}

这里强调一下：dfn [] 数组随访问顺序严格单调递增。其为我们寻找强连通分量奠定基础。在介绍如何寻找强连通分量之前，我们必须用 dfs 对图的边进行分类。图的边分为 4 类：
（1）树边 指深度优先搜索树上的边。具体来说如果没有访问过，接下来要从 v 开始搜索，那么边 u->v 就是树边。
（2）后向边 指将节点 u 连接到其在深度优先搜索树中的祖先节点 v 的边 u->v。我们可以直到，后向边一定有： dfn[v] !=0 && dfn[v] <= dfn[u] 即：v 被访问过，且 v 比 u 先被访问。
（3）前向边 和后向边相反，v 被访问过，且 v 比 u 后被访问。
（4）横向边 所有其他的边被称为横向边满足以下性质 u->v 满足 dfn [u] > dfn [v]。
强连通分量的定义上面已经给出。简单来说一个强连通分量的每两个点可以互相到达，且这个强连通分量的节点数尽可能大。
这里给出一个很重要的定理：若存在后向边 u->v，则 u,v 在同一个强连通分量中
下面正式介绍 Tarjan 算法。我们如何判断一条边是不是后向边：可以看出，后向边 u->v 满足 dfn [v]<=dfn [u]，同时横向边也满足此条件，因此我们不能简单根据 dfn 数组进行判断。
解决：我们考虑维护一个栈，栈中的元素是当前搜索树上的点。显然，如果一条边 u->v 是后向边，那么我们在访问 u 时会发现 v 已经在栈中。然后，如果 dfn [v]<dfn [u]，则 u->v 是后向边。可以定义 instack 数组，节点 u 入栈时 instack [u]=true，出栈时置为 false。在知道了 u->v 是后向边之后，我们再引入一个 low 数组，low [u] 代表包含 u 的 SCC 中第一个被搜索到的节点的 dfn 值，也可以理解为从 u 出发能回溯到的 dfn 最小节点的 dfn 值。显然，若 u->v 是一个后向边，那么 v 是 u 的祖先，v 是 v，u 所在的 SCC 中最先被访问到的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stack>
 
int dfn[MAXN], tot = 0;
bool instack[MAXN];
int low[MAXN];
std::stack<int> stk;
 
void dfs(int u)
{
    dfn[u] = ++tot;
    low[u] = dfn[u]; // 一开始low[u]是自己，有后向边再更新
    stk.push(u);
    instack[u] = true;
    for(int e = first[u]; e; e = nxt[e])
    {
        int v = go[e];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]); // 子节点更新了，我也要更新
            // 若子节点没更新，则min能够保证low[u] == dfn[u]
        }
        else if(instack[v]) // v访问过且在栈中，意味着u→v是后向边
        {
            low[u] = min(low[u], dfn[v]);
            // 此处用min的原因是u→v可能是前向边，此时dfn[v]>dfn[u]
        }
    }
    stk.pop();
    instack[u] = false;
}

最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stack>
 
int dfn[MAXN], tot = 0;
bool instack[MAXN];
int low[MAXN];
int co[MAXN], col = 0;
std::stack<int> stk;
 
void Tarjan(int u)
{
    dfn[u] = ++tot;
    low[u] = dfn[u]; // 一开始low[u]是自己，有后向边再更新
    stk.push(u);
    instack[u] = true;
    for(int e = first[u]; e; e = nxt[e])
    {
        int v = go[e];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]); // 子节点更新了，我也要更新
            // 若子节点没更新，则min能够保证low[u] == dfn[u]
        }
        else if(instack[v]) // v访问过且在栈中，意味着u→v是后向边
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) // 是SCC中的第一个被访问的节点
    {
        co[u] = ++col;
        while(stk.top() != u) co[stk.top()] = col, instack[stk.top()] = false, stk.pop();
            // 染色，弹栈
        instack[u] = false;
        stk.pop(); // 最后把u弹出去
    }
}

参考文献：Tarjan 算法超超超详解

# 字符串

# KMP 算法

KMP 算法主要用来进行判断两个字符串是否 A 是 B 的子串。暴力的解法十分简单，1 只需要一一枚举文本串的起始位置 i 然后和模式串进行逐位匹配即可。

# next 数组

介绍 KMP 算法要先来学习一下 Next 数组。假设有一个字符串 s (下标从 0 开始)，那么它以 i 号位作为结尾的子串就是 s [0…i]。对该子串来说，长度位 k+1 的前缀和后缀分别时 s [0…k] 和 s [i-k…i]。现在定义一个 int 型数组 next，其中 next [i] 表示子串 s [0…i] 的前缀 s [0…k] 等于后缀 s [i-k…i] 的最大的 k (注意前缀和后缀可以部分重叠，但不能是 s [0…i] 本身) 如果找不到相等的前后缀，那么就令 next [i]= -1。显然，next [i] 就是所求最长相等前后缀中前缀最后一位的下标。
这里可以利用递推来进行 Next 数组的求解。假设已经求出了 next [0]~next [i-1]，现在用它们来推出 next [i]。
通过这样可以列出下面伪代码求解过程:

  • ①初始化 next 数组，令 j = next [0] = -1。
  • ②让 i 在 1 ~ len -1 范围遍历，对每一个 i，执行③④，求解 next [i]。
  • ③不断令 j = next [i]，直到 j 回退为 - 1，或者是 s [i] == s [j+1] 成立。
  • ④如果 s [i] == s [j+1]，则 next [i] = j +1; 否则 next [i] = j。
1
2
3
4
5
6
7
8
9
10
11
12
13
void getNext(char s[], int len){
	int j = -1;
	next[0] = -1;    //初始化 j= next[0] = -1
	for(int i = 1; i < len;i++){   //求解 next[1] ~ next[len -1]
		while(j != -1 &&s[i] != s[j+1]){
			j = next[j];   //反复令 j =next[j]
		}   //直到j回退到-1，或是 s[i] == s[j+1]
		if(s[i] == s[j+1]){
			j++;
		}
		next[i] = j;  //令 next[i] = j
	}
}

# KMP 算法

在上文的基础，利用 next 数组即可进行 KMP 算法求解。这里也知晓了 next 数组的含义 ** 即当 j+1 位失配时，j 应该回退到的位置。由此总结除 KMP 算法的一般思路。

  • ①初始化 j = -1, 表示 pattern 当前已经被匹配的最后位。
  • ②让 i 遍历文本串 text，对每一个 i，执行③④来试图匹配 text [i] 和 pattern [j + 1].
  • ③不断令 j =next [j]，直到 j 回退为 -1，或者 text [i] == pattern [j + 1] 成立。
  • ④如果 text [i] == pattern [j + 1], 则令 j++。如果 j 达到 m -1 ，则说明 pattern 是 text 的子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool KMP(char text[], char pattern[]){
	int n =strlen(text), m = strlen(pattern);
	getNext(pattern,m);  //计算pattern 的next 数组
	int j=-1;  //初始化 j = -1 ，表示当前还没有任意一位被匹配
	for(int i =0; i < n; i++){   //视图匹配text[i]
		while(j != -1 && text[i] != pattern[j+1]){
			j = next[j];   //不断回退，直到j 回到 -1 或者 text[i] == pattern[j+1]
		}
		if(text[i] == pattern[j+1]){
			j++;   //text[i] 和pattern[j+1] 匹配成功
		}
		if(j == m -1 ){
			return true;
		}
	}
	return false;
}

这段代码其实和求解 next 数组的代码惊人的相似。其实，求解 next 数组的过程就是模式串 pattern 进行自我匹配的过程。
接着需要考虑 text 中 pattern 串出现的次数。这里考虑的主要是当 pattern 和 text 匹配完成之后，如何进行回退效率最高且不会遗漏解。这时还是利用 next 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMP(char text[], char pattern[]){
	int n =strlen(text), m = strlen(pattern);
	getNext(pattern,m);  //计算pattern 的next 数组
	int ans = 0,j =-1;  //初始化 j = -1 ，表示当前还没有任意一位被匹配
	for(int i =0; i < n; i++){   //视图匹配text[i]
		while(j != -1 && text[i] != pattern[j+1]){
			j = next[j];   //不断回退，直到j 回到 -1 或者 text[i] == pattern[j+1]
		}
		if(text[i] == pattern[j+1]){
			j++;   //text[i] 和pattern[j+1] 匹配成功
		}
		if(j == m -1 ){
			ans++;
			j = next[j]; //让j回退到next[j]继续进行匹配
		}
	}
	return ans; //返回成功匹配次数
}

这里对上述的 KMP 算法还有优化空间，

# 动态规划

【定义】DP 使用来解决一类最优化问题的算法思想。动态规划将一个复杂的问题分解成若干的子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划将每个求结果的子问题的解记录下来，这样当下一次碰到同样的子问题时，就可以直接使用之前的记录的结果，而不是重复计算。一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处也可以称为记忆化搜索。

# 动态规划的递归和递推写法

# 动态规划的递归写法

这里拿斐波那契数列的计算进行举例，正常没有优化的求解如下，根据斐波那契额数列的定义直接写代码：

1
2
3
4
int F(int n){
	if(n == 1|| n == 1) return 1;
	else return F(n-1) + F(n-2);
}

这里事实上会进行很多的重复计算，例如 n = 5 时，F (5) = F (4) + F (3)，但是在计算 F (4) 时对 F (3) 又进行了一次计算。为了避免重复计算，可以开一个一维的 dp 数组，用来保存计算过的结果，这便是记忆化（即记录计算过的数据以此来防止重复计算带来的时间复杂度)

1
2
3
4
5
6
7
8
9
int dp[MAX_N]; //这里可以初始化dp为 -1
int F(int n){
	if(n == 0 || n == 1) return 1;
	if(dp[n] != -1) return dp[n];
	else{
		dp[n] = F(n-1) + F(n-2);
		return dp[n];
	}
}

这样就可以把计算结果记录下来，下次再需要使用时可以省去计算。
通过上面的例子可以引申出一个概念：如果一个问题可以被分解为若干个子问题，并且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。动态规划通过记录重叠子问题的解，来使下次碰到相同的子问题时可以直接使用之前的记录的结果。

# 动态规划的递推写法

用经典的数塔问题为例子。将一些数字排成数塔的形状，其中第一层右一个数字，第二层二个数字，… 第 n 层 n 个数字。现在要从第一层走到第 n 层，每次只能走向下一层连接的两个数字中的一个，需要知道：到达底层将路径上的所有数字相加后得到的和最大是多少。
按照题目的描述，如果卡一个二维数组 f,f [i][j] 存放第 i 层的第 j 个数字。如果尝试琼剧所有路径，然后记录路径上数字和的最大值，那么时间复杂度 O (2n2^n)
数塔
一开始，从第一层的 5 出发，按照 5->8->7 的路线来到 7，并枚举从 7 出发的到达最底层的所有路径。但是，之后按 5->3->7 时，如果没有进行记录，又会去枚举 7 出发的到达最底层的所有路径，这就导致了从 7 出发的到达最底层的所有路径被反复的访问。
由上面的考虑，不妨令 dp [i][j] 表示从第 i 行第 j 个数字出发到达最底层的所有路径中能得到的最大和，例如 dp [3][2] 就是图中的 7 到达最底层的路径最大和。在定义这个数组之后，dp [1][1] 就是我们最终想要的答案。注意到一个细节：如果要求从位置 (1,1) 到达最底层的最大和 dp [1][1]，那么一定要先求出它的两个子问题 " 从位置 (2,1) 到达最底层的最大和 dp [2][1]“和” 从位置 (2,2) 到达最底层的最大和 dp [2][2], 即进行了以此决策：走数字 5 的左下还是右下。写出式子就是： dp[1][1]=max(dp[2][1],dp[2][2])+f[1][1] 由此可以打的这么一个信息，如果要求出 dp [i][j]，那么一定要先求出它的两个子问题。即 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j] 。把 dp [i][j] 称为问题的状态，而把上面的式子称为状态转移方程。
下面根据这种思想写出动态规划的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000;
int f[maxn][maxn],dp[maxn][maxn];
int main(){
	int n;
	scanf("%d",&n);
	for(int i =1;i<=n;i++){
		for(int j = 1; j <= i; j++){
			scanf("%d",&f[i][j]); //输入数塔
		}
	}
	for(int j = 1;j<= n;j++){
		dp[n][j] = f[n][j];
	}
	for(int i =n - 1; i >- 1; i--){
		for(int j =1; j <= i; j++){
			dp[i][j] = max(dp[i + 1][j],dp[i+1][j+1]+f[i][j]);
		}
	}
	printf("%d\n",dp[1][1]);
	return 0;
}

显然，使用递归也可以实现上面的例子 (即从 dp [1][1] 开始递归，直至到达边界时返回结果)。二者的区别在于：使用递推写法的计算方式是自底向上，即从边界开始，不断向上解决问题，直到解决了目标问题：而使用递归写法的计算方式是自顶向下，即从目标问题开始，将它分解成子问题的组合，直到分解到边界为止。通过上面的例子再引申一个概念：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构。最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。因此，一个问题必须拥有最优子结构，才能使用动态规划去解决。即，一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。
①：分治和动态规划。分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解。但是不同的是，分治法分解出的子问题是不重叠的，因此分治法解决的问题不拥有重叠子问题，二动态规划解决的问题拥有重叠子问题。例如：归并排序和快速排序都是分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此，它们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的问题是最优化问题。
②：贪心和动态规划。贪心和动态规划都要求原问题必须拥有最优子结构。二者的区别在于，贪心法采用的计算方式类似上面介绍的 “自顶向下”。但是并不等待子问题求解完毕后在选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题就不去求解了，直接抛弃。也就是说，它总是在上一步选择的基础上继续选择，因此整个过程以一种单链的流水方式进行，

# 最大连续子序列和

问题如下： 给定一个数字序列A1A_1,A2A_2,…,AnA_n 求 i，j 使得AiA_i+…+AjA_j 最大，输出这个最大的和。
这个问题可以用暴力，就是直接枚举左右端点 O (n2n^2) 的复杂度，而计算 A [i] - A [j] 需要 O (n) 复杂度因此总复杂度较高。下面介绍动态规划的做法，复杂度仅为 O (n)。
步骤 1： 令状态 dp [i] 表示以 A [i] 作为末尾的连续序列的最大和。以样例为例子：序列 - 2 11 -4 13 -5 -2, 下标分别记为 0,1,2,3,4,5, 那么：
dp[0]=-2,dp[1]=11,dp[2]=7(11-4),dp[3]=20,dp[4]=15,dp[5]=13 通过设置这么一个 dp 数组，要求的最大和其实就是 dp [0]–dp [n-1] 中的最大值。下面解释如何求解 dp 数组。
步骤 2：作如下考虑：因为 dp [i] 要求是必须以 A [i] 结尾的连续序列，那么有两种情况：
①：这个最大和的连续序列只有一个元素，即以 A [i] 开始，A [i] 结尾。
②：这个最大和的连续序列有多个元素，即从前面某处 A [p] 开始 (p<i), 一直到 A [i] 结尾。
第一种情况，最大和就是 A [i] 本身。
第二种情况，最大和是 dp [i-1]+A [i] 由此可以得到状态转移方程:
dp[i] = max{A[i], dp[i-1] + A[i]}

# 最长不下降子序列 (LIS)

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降的。

例如，现在有序列 A = {1,2,3,-1,-2,7,9}(下标从 1 开始)，它的最长不下降子序列是 {1,2,3,7,9}, 长度为 5. 另外，还有一些子序列是不下降子序列，比如 {1,2,3},{-2,7,9} 等，但都不是最长的。
其实这个问题很容易想到也可以直接暴力求解，直接对所有情况进行枚举，但是其复杂度显然很高。我们仍利用 dp [i] 数组来进行辅助记录。如果令 dp [i] 表示以 A [i] 结尾的最长不下降子序列长度。这样对 A [i] 来说就会有两种可能:
①：如果存在 A [i] 之前的元素 A [j](j<i)，使得 A [j]<=A [i] 且 dp [j]+1 > dp [i]，那么就把 A [i] 跟在以 A [j] 结尾的 LIS 后面，形成一条更长的不下降子序列。
②：如果 A [i] 之前的元素都比 A [i] 大，那么 A [i] 就只好自己形成一条 LIX，但是长度为 1，即这个子序列里面只有一个 A [i]。
因此可以写出状态转移方程： dp[i] = max{1,dp[j] + 1}
由此可以写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 100;
int A[N],dp[N];
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
		scanf("%d", &A[i]);
	}
	int ans = -1;
	for(int i = 1; i <= n;i++){
		dp[i] = 1;
		for(int j = 1;j < i ;j++){
			if(A[i] >= A[j] && (dp[j] + 1 > dp[i])){
				dp[i] = dp[j] +1;
			}
		}
		ans = max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

上述算法的时间复杂度为 O (n2n^2)，但事实上有 O (n Logn) 的做法。
将原来的 dp 数组的存储由数值换成该序列中，上升子序列长度为 i 的上升子序列的最小末尾数值，这其实就是一种几近贪心的思想：我们当前上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测地，可作为结果地上升子序列之中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=0x7fffffff;
		//初始值要设为INF
		/*原因很简单，每遇到一个新的元素时，就跟已经记录的f数组当前所记录的最长
		上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到
		一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个q，INF
                就是为了方便向后替换啊！*/ 
	}
	f[1]=a[1];
	int len=1;//通过记录f数组的有效位数，求得个数 
	/*因为上文中所提到我们有可能要不断向前寻找，
	所以可以采用二分查找的策略，这便是将时间复杂
    度降成nlogn级别的关键因素。*/ 
	for(int i=2;i<=n;i++)
	{
		int l=0,r=len,mid;
		if(a[i]>f[len])f[++len]=a[i];
		//如果刚好大于末尾，暂时向后顺次填充 
		else 
		{
		while(l<r)
		{	
		    mid=(l+r)/2;
		    if(f[mid]>a[i])r=mid;
	//如果仍然小于之前所记录的最小末尾，那么不断
	//向前寻找(因为是最长上升子序列，所以f数组必
	//然满足单调) 
			else l=mid+1; 
		}
		f[l]=min(a[i],f[l]);//更新最小末尾 
     	}
    }
    cout<<len;

# 最长公共子序列 （LCS）

题目描述： 给定两个字符串 A 和 B，求一个字符串，使得这个字符串是 A 和 B 的最长公共部分（子序列可以不连续）
这里令 dp [i][j] 表示字符串 A 的 i 号位和字符串 B 的 j 号位之前的 LCS 长度，那么可以根据 A [i] 和 B [j] 的情况，分为两种决策：
①若 A [i] == B [j]，则字符串 A 和 字符串 B 的 LCS 增加了 1 位，即有 dp [i][j] = dp [i-1][j-1]+1。
②若 A [i] != B [i]，则字符串 A 的 i 号位和字符串 B 的 j 号位之前的 LCS 无法延长，因此 dp [i][j] 将会继承 dp [i-1][j] 与 dp [i][j] 中较大的值，即有 dp [i][j] = max {dp [i-1][j],dp [i][j-1]}。

# 背包问题

背包问题是一类很经典的动态规划问题，这里先介绍两个最简单的背包问题：0-1 背包问题和完全背包问题。

# 01 背包问题

题目描述：有 n 件物品，每件物品的重量为 w [i]，价值为 c [i]。现有一个容量为 V 的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有 1 件。

这里引入 dp [i][v] 表示前 i 件物品恰好装入容量为 v 的背包中所获得的最大值。下面介绍如何求解 dp 数组。
考虑对第 i 件物品有两种选择策略：
①不放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量为 v 的背包中所能获得的最大价值，也即 dp [i-1][v]。
②放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量 v-w [i] 的背包中所能获得的最大价值，也即 dp [i-1][v-w [i]]+c [i]。
由上述两种策略，且要获得最大价值，有下面状态转移方程 dp [i][v] = max {dp [i-1][v],dp [i-1][v-w [i]]+c [i]}。

1
2
3
4
5
for(int i = 1;i<=n;i++){
	for(int v = w[i]; v<= V;v++){
		dp[i][v] = max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
	}
}

当然，可以对空间进行优化，可以将其化简为 dp [v] = max (dp [v],dp [v-w [i]]+c [i])。 不过这样写需要更改循环代码。

1
2
3
4
5
for(int i = 1;i<=n;i++){
	for(int v = V; v>=w[i];v--){
		dp[v] = max(dp[v],dp[v-w[i]]+c[i]);
	}
}

# 完全背包问题

描述如下：有 n 种物品，每种物品的重量为 w [i]，价值为 c [i]。现有一个容量为 V 的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。每种物品都有无穷件。

可以看出，完全背包问题和 01 背包问题唯一的区别就在于：完全背包的物品数量每种有无穷件，选取物品时对每一件物品可以取多件。同样令 dp [i][v] 表示前 i 件物品恰好放入容量为 v 的背包中能获得的最大价值。对第 i 件物品来说：
①不放第 i 件物品，那么 dp [i][v]=dp [i-1][v]，这跟 01 背包是一样的。
②放第 i 件物品。这里的处理和 01 背包有所不同，因为 01 背包的每个物品只能选择一个，因此选择放第 i 件物品就意味着必须转移到 dp [i-1][v-w [i]] 这个状态；但是完全背包不同，完全背包如果选择放第 i 件物品之后并不是转移到 dp [i-1][v-w [i]]，而是转移到 dp [i][v-w [i]] 这个状态，因为每件物品都可以放任意件，放了第 i 件物品之后还可以继续放第 i 件物品，直到第二维的 v-w [i] 无法保持大于等于 0 为止。
由上面的分析可以写出状态转移方程： dp[i][v] = max(dp[i-1][v],dp[i][v-w[i]]+c[i]) 。
写成一维形式之后和 01 背包完全相同，唯一的区别是这里的 v 的枚举顺序是正向枚举，而 01 背包的一维形式中必须 v 是逆向枚举。

1
2
3
4
5
for(int i = 1; i <= n; i++){
	for(int v  = w[i], v <= V; v++){
		dp[v] = max(dp[v],dp[v-w[i]]+c[i]);
	}
}

# 状态压缩 DP

这里讲一个之前某蓝桥杯用到的算法，虽然很容易爆内存，但是有些实在没有思路的题可能用一下也是可以的。

# 扩展的一些算法或者数据结构

# 排序

# 归并排序

思路参考：排序 —— 归并排序（Merge sort）-CSDN 博客
直接

# 二分

# 二分查找

首先肯定是最经典的 从有序数组中查找某个值。

给定长度为 n 的单调不下降数列a0a_0,…an−1a_{n-1} 和一个数 k，求满足aia_i >= k 条件的最小 i。不存在的情况下输出 n。

当然，可以朴素地按照顺序逐个查找。但是如果利用二分地算法可以降低到 O (lognlog_n) 的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n,k;
int a[MAX_N];
void solve(){
	int lb = -1, ub =n;
	while(ub - lb > 1){
		int mid = (lb + ub) /2;
		if(a[mid] >= k){
			ub = mid;
		} else{
			lb =mid;
		}
	}
	printf("%d\n",ub);
}

这种算法被称为二分搜索。此外 STL 以 lower_bound 函数的形式也实现了二分搜索。
下面还有一道题，刚看到时总感觉手足无措，感觉暴力不行又没有其他办法，这时使用二分能很好地解决问题。

有 N 条绳子，长度分别为LiL_i。如果从他们中切割出 K 条长度相同的绳子的话，这 K 条绳子每条最长能有多长？答案保留小数点后 2 位。

让我们试着套用二分搜索的模型解决这个问题：条件 C (x):= 可以得到 K 条长度为 x 的绳子。
则问题变成了满足 C (x) 的条件的最大 x。在区间初始化时，只需要充分大的数 INF 作为上界即可: lb =0,ub = INF
现在的问题是是否可以高效判断 C (x)。由于长度为LiL_i 的绳子最多可以切除 floor (LiL_i /x) 段长度为 x 的绳子，因此：C (x) = floor (LiL_i/x) 的总和是否大于等于 k。 者可以在 O (n) 的时间内被判断出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int N,k;
double L[MAX_N];
bool C(double x){
	int num = 0;
	for(int i = 0; i <N; i++){
		num += (int)(L[i] / x);
	}
	return num>=K;
}

void solve(){
	double lb =0, ub =INF;
	for(int i =0; i<100;i++){
		double mid = (lb + ub) /2;
		if(C(mid)) lb = mid;
		else ub = mid;
	}
	printf("%.2f\n",floor(ub*100)/100);
}

# 不止查找 - 二分应用

# 最大化平均值

n 个物品的价值分别是wi和viw_i和v_i。从中选出 k 个物品使得单位重量的价值最大。

思路挺简单的，最大单位重量价值不超过题目给定最大价值直接利用二分 l=0,r=max_value。check 函数上直接检测能否用当前值进行判断即可。这里给出计算公式
∑i=1n(vi)\sum\limits_{i=1}^n(v_i)/∑i=1n(wi)\sum\limits_{i=1}^n(w_i) >= x
可以转变为： ∑i=1n(vi−x∗wi)\sum\limits_{i=1}^n(v_i - x* w_i) >= 0 便于写 check 函数。

# 线段树

线段树是擅长处理区间的，形如下图的数据结构。线段树是一棵完美二叉树，（所有叶子的深度都相同，每个系欸但要不是叶子要么是有两个儿子的树），树上的每个节点都维护一个子区间。当有 n 个元素时，对区间的操作可以在 O (log n) 的时间内完成。
线段树演示
根据节点中维护的数据的不同，线段树可以提供不同的功能。下面实现了基于 RMQ 操作的线段树。

# 基于线段树的 RMQ 结构

下面要建立的线段树在给定数列a0a_0,a1a_1,…an−1a_{n-1}, 的情况下，可以在 O (log n) 时间内完成如下两种操作

  • 给定 s 和 t，求asa_s,as+1a_{s+1},…,ata_t 的最小值
  • 给定 i 和 x，把aia_i, 的值改成 x
    如下图，线段树的每个节点维护对应区间的最小值。在建树时，只需要按从下到上的顺序分别取左右儿子的值中较小者就可以了。

# 基于线段树的 RMQ 查询

如果要求a0a_0,…,a6a_6 的最小值。我们只需要求出下图中的三个节点的值的最小值即可。