L2~L3部分（第一阶段）考点解析 + 知识点预习-171主机测评

本节概要：

课程链接：戳这 <—（您的支持是我最大的动力！）

一、最短路（dijkstra、floyd）

1、图的存储：

邻接矩阵

for(int i=1;i<=m;i++){ // 输入m条边，进行存图操作
int u,v,w;
cin>>u>>v>>w;
g[u][v]=w; // u点到v点有一条边，边权为w
}

邻接表

for(int i=1;i<=m;i++){ // 输入m条边，进行存图操作
int u,v,w;
cin>>u>>v>>w;
c[u].push_back({v,w}); // u点到v点有一条边，边权为w
}

存边和存树、图的区别

for(int i=1;i<=m;i++){ // 没有相连的关系是存边，单纯用数组存下来
cin>>u[i]>>v[i]>>w[i];
}

for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
c[u].push_back({v,w}); // 有相连的关系是存树和图
}

2、单源最短路 dijkstra 堆优化模板：

算法思路：

堆优化版的 dijkstra 是对朴素版 dijkstra 进行了优化，在朴素版 dijkstra 中时间复杂度最高的寻找距离最短的点

(

)

O(n^2)

$O (n^{2})$ 可以使用最小堆优化。

1. 一号点的距离初始化为零，其他点初始化成无穷大。

2. 将一号点放入堆中。

3. 不断循环，直到堆空。每一次循环中执行的操作为：

弹出堆顶（与朴素版 dijkstra 找到
用该点更新临界点的距离，若更新成功就加入到堆中。

时间复杂度分析：

寻找路径最短的点：

O

(

n

)

O(n)

$O (n)$
加入集合

S

S

$S$ ：

O

(

n

)

O(n)

$O (n)$
更新距离：

O

(

m

l

o

g

n

)

O(mlogn)

$O (m l o g n)$

参考模板：

int dijkstra()
{
for(int i=1;i<=n;i++) d[i]=1e18; // 初始化d数组
priority_queue<PII,vector<PII>,greater<PII>> q; // 定义优先队列（小根堆，距离优先）
q.push({0,1}); // 把起点放进去
d[1]=0; // 起点距离为0

while(q.size()){
auto p=q.top(); // 取出当前点
q.pop();
int u=p.y; // 当前点为第二个关键字
if(st[u]) continue;
st[u]=true; // 标记重复点
for(auto p:c[u]){ // 判断与u点相连的其他点是否能被更新
int v=p.x;
int w=p.y;
if(d[v]>d[u]+w){ // 如果能被更新
d[v]=d[u]+w; // 更新最短距离
q.push({d[v],v}); // 并且把点放进队列里面更新其他点
}
}
}

if(d[n]==1e18) d[n]=–1; // 如果没连通，输出-1
return d[n]; // 否则输出最短距离
}

3、多源最短路 floyd 模板：

算法思路：

f

[

i

,

j

]

f[i, j]

$f [i, j]$ 表示从

i

i

$i$ 走到

j

j

$j$ 的路径上除

i

i

$i$ 和

j

j

$j$ 点外只经过

1

1

$1$ 到

n

n

$n$ 的点

k

k

$k$ 的所有路径的最短距离。
那么根据中间点

k

k

$k$ 更新其他点的距离：

f

[

i

,

j

]

=

m

i

n

(

f

[

i

,

j

]

f[i, j] = min(f[i, j]

$f [i, j] = min (f [i, j]$ ,

f

[

i

,

k

]

+

f

[

k

,

j

]

)

f[i, k] + f[k, j])

$f [i, k] + f [k, j])$ 。
因此在计算第

k

k

$k$ 层的

f

[

i

,

j

]

f[i, j]

$f [i, j]$ 的时候必须先将第

k

−

1

k – 1

$k - 1$ 层的所有状态计算出来，所以需要把

k

k

$k$ 放在最外层。
时间复杂度分析：

O

(

n

3

)

O(n^3)

$O (n^{3})$

参考模板：

void floyd()
{
for(int k=1;k<=n;k++){ // 枚举中间经过点
for(int i=1;i<=n;i++){ // 枚举起点
for(int j=1;j<=n;j++){ // 枚举终点
g[i][j]=min(g[i][j],g[i][k]+g[k][j]); // 动态更新
}
}
}
}

二、最小生成树

例题：Kruskal 算法

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数

$N$ ,

$M$ ，表示该图共有

$N$ 个结点和

$M$ 条无向边。

接下来

$M$ 行每行包含三个整数

X_i

$X_{i}$ ,

Y_i

$Y_{i}$ ,

Z_i

$Z_{i}$ ，表示有一条长度为

Z_i

$Z_{i}$ 的无向边连接结点

X_i

$X_{i}$ ,

Y_i

$Y_{i}$ 。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出

数据规模：

≤

5000

，

≤

，

≤

，

≤

1≤N≤5000，1≤M≤2×10^5，1≤Z_i≤10^5，1≤X_i,Y_i≤N

$1 \leq N \leq 5000 ， 1 \leq M \leq 2 \times 1 0^{5} ， 1 \leq Z_{i} \leq 1 0^{5} ， 1 \leq X_{i}, Y_{i} \leq N$

思路：

将所有边按照权值的大小进行升序排序，然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。直到具有

n

n

$n$ 个顶点的连通网筛选出来

n

−

1

n-1

$n - 1$ 条边为止，筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：使用并查集，在初始状态下给各个个顶点在不同的集合中。
遍历过程的每条边，判断这两个顶点的是否在一个集合中，如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要；如果不在一个集合中，则要这条边。

图片描述

struct Node{ // 存边结构体
int u,v,w;
}g[N];

bool cmp(Node a,Node b){ // 自定义排序函数
return a.w<b.w;
}

int find(int x) // 并查集find函数
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}

void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>g[i].u>>g[i].v>>g[i].w; // 存边
sort(g+1,g+m+1,cmp); // 按边权从小到大排序
int sum=0,cnt=1;
for(int i=1;i<=n;i++) f[i]=i; // 并查集初始化
for(int i=1;i<=m;i++){ // 从小到大枚举边
int a=find(g[i].u);
int b=find(g[i].v);
if(a!=b){ // 判断边是否连通
f[a]=b;
sum+=g[i].w; // 不连通就加上这条边和边权
cnt++;
}
}
if(cnt!=n) cout<<"impossible"<<'\\n'; // 最后判断是否能构成最小生成树
else cout<<sum<<'\\n'; // 如果可以就输出最小边权和
}

三、L3部分注意事项

陈越姥姥原话（天梯赛执剑者）：天梯第三级，一般图论模板题是起步难度，另外两题看出题人的心情，想出多难都可以，让 ACM-ICPC 金牌选手 30 分钟内不能做出就可以。不是天神级别的娃，就佛了吧。～(￣▽￣～)~

所以对于 L3 级别的题目，我们有时间（在做完 L1 和 L2 还有时间的情况下）能做的尽量做，能骗分就尽量骗分，这个是冲刺个人国二和国一的必经之路（当然如果只想冲个人国奖 175+ 的就老老实实先把 L1 和 L2 做好吧）。

四、01背包、完全背包

1. 背包问题求解

最基本的背包问题就是

$01$ 背包问题

（

）

（01 knapsack problem）

$（ 01 k na p s a c k p r o b l e m ）$ ：一共有

$N$ 件物品，第

$i$ （

$i$ 从

$1$ 开始）件物品的重量为

[

]

w[i]

$w [i]$ ，价值为

[

]

v[i]

$v [i]$ 。在总重量不超过背包承载上限

$W$ 的情况下，能够装入背包的最大价值是多少？

$01$ 背包问题为啥不适用贪心算法：假设背包容量为

50kg

$50 k g$ ，物品

1, 2, 3

$1, 2, 3$ 的容量和价值分别为（

10kg

$10 k g$ ,

$60$ ），（

20kg

$20 k g$ ,

100

$100$ ）和（

30kg

$30 k g$ ,

120

$120$ ）。

单位重量价值最高的为物品

，

1，6/kg

$1 ， 6/ k g$ 。但是依照贪心算法首选物品

$1$ 却不能获得最优解：

图片描述

如果采用暴力穷举的方式，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是

(

)

O(2^N)

$O (2^{N})$ ，这是不可接受的。进而才需要动态规划的解法来进行优化！

背包问题是动态规划

（

）

（DP）

$（ D P ）$ 里的非常重要的一部分，关于几种常见的背包如下：

01背包问题：每种物品只有一个，可以选择放或不放。
完全背包问题：每种物品有无限个，可以选择放任意个。
多重背包问题：每种物品有有限个，可以选择放任意个但不能超过给定的数量。
混合三种背包问题：每种物品可能属于以上三种情况之一。
二维费用的背包问题：每种物品除了重量还有另一种费用，背包也有相应的限制。
分组的背包问题：物品分为若干组，每组只能选择一个物品放入背包。
有依赖的背包问题：物品之间存在依赖关系，例如要放某个物品必须先放另一个物品。

2. 动态规划的原理

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。

但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

最优性原理是动态规划的基础，最优性原理是指 “多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略” 。

3. 背包问题的解决过程

在解决问题之前，首先定义一些变量：

V_i

$V_{i}$ 表示第

$i$ 个物品的价值，

W_i

$W_{i}$ 表示第

$i$ 个物品的体积，定义

(

)

f(i,j)

$f (i, j)$ ：当前背包容量

$j$ ，前

$i$ 个物品最佳组合对应的价值，同时背包问题抽象化（

，

…

，

X_1，X_2，…，X_n

$X_{1} ， X_{2} ， \dots ， X_{n}$ ，其中

X_i

$X_{i}$ 取

$0$ 或

$1$ ，表示第

$i$ 个物品选或不选）。

① 建立模型，即求

(

…

)

max(f_1X_1+f_2X_2+…+f_nX_n)

$ma x (f_{1} X_{1} + f_{2} X_{2} + \dots + f_{n} X_{n})$ ；

② 寻找约束条件，

…

≤

总

W_1X_1+W_2X_2+…+W_nX_n \\leq W_总

$W_{1} X_{1} + W_{2} X_{2} + \dots + W_{n} X_{n} \leq W_{总}$ ；

③ 寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即 $\\{f(i-1,j)，f(i-1,j-w(i))+v(i)\\} f(i,j)=max{f(i−1,j)，f(i−1,j−w(i))+v(i)}。$

其中

由此可以得出递推关系式：

当
当 $f(i,j)=max\\{f(i-1,j)，f(i-1,j-w(i))+v(i)\\} f(i,j)=max{f(i−1,j)，f(i−1,j−w(i))+v(i)}；$

那么如果要到达

(

)

f(i,j)

$f (i, j)$ 这一个状态有几种方式？

肯定是两种！第一种是第

$i$ 件商品没有装进去，第二种是第

$i$ 件商品装进去了。

没有装进去很好理解，就是

(

−

)

f(i-1,j)

$f (i - 1, j)$ ；装进去了怎么理解呢？如果装进去第

$i$ 件商品，那么装入之前是什么状态，肯定是

(

−

(

)

f(i-1,j-w(i))

$f (i - 1, j - w (i))$ 。由于最优性原理（上文讲到），

(

−

(

)

f(i-1,j-w(i))

$f (i - 1, j - w (i))$ 就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优（相当于更新当前的状态）。

回到最初的

$01$ 背包问题：有

$n$ 个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：

＝

，

总

＝

n＝4，W_总＝8

$n ＝ 4 ， W_{总} ＝ 8$ ：

	2	3	4	5
	3	4	5	6

然后一行一行的填表（如下图）：

如此下去，填到最后一个， $f(4,8)=max\\{f(4-1,8)，f(4-1,8-w(4))+v(4)\\}=10…… f(4,8)=max{f(4−1,8)，f(4−1,8−w(4))+v(4)}=10……$
表格填完，最优解即是 $f(n,W_总)=f(4,8)=10 f(n,W总)=f(4,8)=10。$

所以填完表如下图：

图片描述

#include<iostream>
#include <algorithm>

using namespace std;

int f[5][9]; //动态规划表
int w[5]={0,2,3,4,5}; //商品的体积2、3、4、5
int v[5]={0,3,4,5,6}; //商品的价值3、4、5、6
int W=8; //背包大小

int main()
{
for(int i=1;i<=4;i++){
for(int j=1;j<=W;j++){
if(j<w[i]) f[i][j]=f[i–1][j];
else f[i][j]=max(f[i–1][j],f[i–1][j–w[i]]+v[i]);
}
}
for(int i=0;i<5;i++){ //动态规划表的输出
for(int j=0;j<9;j++) cout<<f[i][j]<<' ';
cout<<endl;
}
return 0;
}

4. 滚动数组优化

上述的方法，我们使用二维数组

[

]

[

]

f[i][j]

$f [i] [j]$ 保存中间状态，这里我们可以使用一维数组

[

]

f[v]

$f [v]$ 保存中间状态就能得到结果：

我们现在使用

在回顾下之前讲过的状态转移方程：

f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

我们可以看到，要想得到

[

]

[

]

f[i][j]

$f [i] [j]$ ，我们需要知道

[

−

]

[

]

f[i-1][j]

$f [i - 1] [j]$ 和

[

−

]

[

−

[

]

f[i-1][j-w[i]]

$f [i - 1] [j - w [i]]$ ，由于我们使用二维数组保存中间状态，所以可以直接取出这两个状态。

当我们使用一维数组存储状态时，

f

[

j

]

f[j]

$f [j]$ 表示，在执行

i

i

$i$ 次循环后(此时已经处理

i

i

$i$ 个物品)，前

i

i

$i$ 个物体放到容量

v

v

$v$ 时的最大价值，即之前的

f

[

i

]

[

j

]

f[i][j]

$f [i] [j]$ 。与二维相比较，它把第一维隐去了，但是二者表达的含义还是相同的，只不过针对不同的

i

i

$i$ ，

f

[

j

]

f[j]

$f [j]$ 一直在重复使用，所以，也会出现第

i

i

$i$ 次循环可能会覆盖第

i

−

1

i-1

$i - 1$ 次循环的结果。
为了求

f

[

j

]

f[j]

$f [j]$ ，我们需要知道，前

i

−

1

i-1

$i - 1$ 个物品放到容量

j

j

$j$ 的背包中带来的收益，即之前的

f

[

i

−

1

]

[

j

]

f[i-1][j]

$f [i - 1] [j]$ 和前

i

−

1

i-1

$i - 1$ 件物品放到容量为

j

−

w

[

i

]

j-w[i]

$j - w [i]$ 的背包中带来的收益，即之前的

f

[

i

−

1

]

[

j

−

w

[

i

]

]

+

v

[

i

]

f[i-1][j-w[i]]+v[i]

$f [i - 1] [j - w [i]] + v [i]$ 。

难点：由于我们只使用一维数组存储，则在求这两个子问题时就没有直接取出那么方便了，因为，第

$i$ 次循环可能会覆盖第

−

i-1

$i - 1$ 次循环的结果。

图片描述

在这里，我们枚举背包容量会有两种顺序枚举：增序和降序

那么这两种顺序有什么区别呢？

增序枚举背包容量会达到什么效果：它会重复的装入某个物品（符合完全背包的性质），而且尽可能多的，使价值最大，当然不会不超过背包容量；
而逆序枚举背包容量：背包中的物品至多装一次（符合

01

01

$01$ 背包的性质），使价值最大，当然不会不超过背包容量；

那么在

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;

int n,W;
int v[N],w[N],f[N];

int main()
{
cin>>n>>W;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=W;j>=v[i];j—) // 01背包需要降序枚举背包容量j
f[j]=max(f[j],f[j–v[i]]+w[i]);
cout<<f[W]<<endl;
return 0;
}

完全背包代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;

int n,W;
int v[N],w[N],f[N];

int main()
{
cin>>n>>W;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=W;j++) // 完全背包需要降序枚举背包容量j
f[j]=max(f[j],f[j–v[i]]+w[i]);
cout<<f[W]<<endl;
return 0;
}

五、线性dp、状态机模型

1. 线性

线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性

$d p$ 」），如下图所示。

图片描述

$d p$ 的线性模型指的是状态转移有明显线性顺序（如一维二维数组、队列、栈等）的

$d p$ ，包括背包问题也是线性

$d p$ 。

2. 线性

对于一个题目，我们要使用

$d p$ ，需要满足以下三个特征：

最优子结构，可以从子问题的解推出全局解。

无后效性，后面的状态对之前的状态没有影响。

有重叠状态，这样才可以通过

DP\\ Table

$D P T ab l e$ 降低复杂度。

一个动态规划问题的解决，有三个步骤：

设计状态：对于基础线性

d

p

dp

$d p$ ，一般由题意直接得出状态。或者有一些套路，如设 $ dp_i$ 表示前

i

i

$i$ 个的答案。
状态转移：按照题意手推。要注意状态转移方程的正确。
递推：有两种大方向，填表或刷表。有些时候不同的方向可能造成思维难度的差异。

现实中，除了少量问题（如：

下面我们就介绍几种常见的线性

「数字三角形线性转移

d

p

dp

$d p$ 模型」
「最长上升子序列（

L

o

n

g

e

s

t

I

n

c

r

e

a

s

i

n

g

S

u

b

s

e

q

u

e

n

c

e

Longest\\ Increasing\\ Subsequence

$L o n g es t I n cr e a s in g S u b se q u e n ce$ ，简称

L

I

S

LIS

$L I S$ ）」
「最长公共子序列（

L

o

n

g

e

s

t

C

o

m

m

o

n

S

u

b

s

e

q

u

e

n

c

e

s

Longest\\ Common\\ Subsequences

$L o n g es t C o mm o n S u b se q u e n ces$ ，简称

L

C

S

LCS

$L C S$ ）」

3. 数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动当前结点至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使得路径上的数字的和最大。

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输入格式第一行包含整数

$n$ ，表示数字三角形的层数。接下来

$n$ 行，每行包含若干整数，其中第

$i$ 行表示数字三角形第

$i$ 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

≤

500

；

−

10000

≤

三角形中的整数

≤

10000

1≤n≤500；−10000≤三角形中的整数≤10000

$1 \leq n \leq 500 ； - 10000 \leq 三角形中的整数 \leq 10000$ ；

输入样例：

4
7
3 8
8 1 0
2 7 4 4

输出样例：

思路：将数字三角形按照行、斜列顺序从

$1$ 开始编号

状态定义：

[

]

[

]

f[i][j]

$f [i] [j]$ 表示从起点走到

[

]

[i,j]

$[i, j]$ 点的所有路径数字的最大值

状态转移：

来自左上方：
来自右上方：
则状态转移方程为：

边界处理及初始化：

由于出现
由于是取
初始化起点：

#include <bits/stdc++.h>
using namespace std;
const int N=1010;

int n,a[N][N],f[N][N];

int main()
{
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j];
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=–2e9; // 初始化1
f[1][1]=a[1][1]; // 初始化2
for(int i=2;i<=n;i++){ // dp转移
for(int j=1;j<=i;j++){
f[i][j]=max(f[i–1][j],f[i–1][j–1])+a[i][j];
}
}
int ans=–2e9;
for(int i=1;i<=n;i++) ans=max(ans,f[n][i]); // 最后一层最大的值就是答案
cout<<ans;
return 0;
}

第二种解法：从下往上

这种做法能规避掉边界问题，不用初始化，代码更简洁。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;

int n,g[N][N],dp[N][N];

int main()
{
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>g[i][j];
for(int i=n;i>=1;i—)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+g[i][j];
cout<<dp[1][1]<<endl;
return 0;
}

六、LIS（最长上升子序列）

给定一个长度为

$N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式：第一行包含整数

$N$ 。第二行包含

$N$ 个整数，表示完整序列。

输出格式：输出一个整数，表示最大长度。

数据范围：

≤

1000

，

−

≤

值域

≤

1≤N≤1000，−10^9≤值域≤10^9

$1 \leq N \leq 1000 ， - 1 0^{9} \leq 值域 \leq 1 0^{9}$ ；

输入样例：

7
3 1 2 1 8 5 6

输出样例：

思路：利用一个状态变量

[

]

f[i]

$f [i]$ 记录最长上升子序列的长度。

从无序数组 $f[i]=f[j]+1\\ \\ (1 \\leq j < i) f[i]=f[j]+1 (1≤j<i)；$

这样我们可以给出状态转移方程：

[

]

(

[

]

[

]

)

(

≤

)

f[i] = max(f[i],f[j]+1)\\ \\ (1 \\leq j < i).

$f [i] = ma x (f [i], f [j] + 1) (1 \leq j < i) .$

注意：状态转移方程需要满足：

由小推大（最优子结构）
由过去推现在（无后效性）

时间复杂度是 $O(n^2) O(n2)$

#include <bits/stdc++.h>
using namespace std;
const int N=1010;

int a[N],f[N],n;

int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int sum=0;
for(int i=0;i<n;i++){
f[i]=1; // 初始长度为1
for(int j=0;j<i;j++){
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1); // 状态转移
}
sum=max(sum,f[i]); // 答案是以所有数为结尾位置的最大值
}
cout<<sum<<endl;
return 0;
}

本节概要：

课程链接：戳这 <—（您的支持是我最大的动力！）

一、最短路（dijkstra、floyd）

1、图的存储：

2、单源最短路 dijkstra 堆优化模板：

算法思路：

时间复杂度分析：

参考模板：

3、多源最短路 floyd 模板：

算法思路：

参考模板：

二、最小生成树

例题：Kruskal 算法

输入格式

输出格式

输入输出样例

思路：

三、L3部分注意事项

四、01背包、完全背包

1. 背包问题求解

2. 动态规划的原理

3. 背包问题的解决过程

其中 f ( i − 1 , j ) f(i-1,j) f(i−1,j) 表示不装， f ( i − 1 , j − w ( i ) ) + v ( i ) f(i-1,j-w(i))+v(i) f(i−1,j−w(i))+v(i) 表示装了第 i i i 个商品，背包容量减少 w ( i ) w(i) w(i)，但价值增加了 v ( i ) v(i) v(i)；

然后一行一行的填表（如下图）：

4. 滚动数组优化

在这里，我们枚举背包容量会有两种顺序枚举：增序和降序

那么在 01 01 01 背包则需要降序枚举背包容量 j j j。

01 01 01背包代码：

完全背包代码：

五、线性dp、状态机模型

1. 线性 d p dp dp 简介

2. 线性 d p dp dp 问题分析

现实中，除了少量问题（如： L I S 、 L C S 、 L C I S LIS、LCS、LCIS LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。

下面我们就介绍几种常见的线性 d p dp dp 模型：

3. 数字三角形

输出格式

第二种解法：从下往上 d p dp dp，起点位置就是答案；

这种做法能规避掉边界问题，不用初始化，代码更简洁。

六、LIS（最长上升子序列）

时间复杂度是 O ( n 2 ) O(n^2) O(n2)

七、真题模拟

例题一：L2-036 网红点打卡攻略 分数 25

例题二：L2-001 紧急救援 分数 25

例题三：L3-001 凑零钱 分数 30

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

其中

那么在

1. 线性

2. 线性

现实中，除了少量问题（如：

下面我们就介绍几种常见的线性

第二种解法：从下往上

时间复杂度是 $O(n^2) O(n2)$

例题一：L2-036 网红点打卡攻略分数 25

例题二：L2-001 紧急救援分数 25

例题三：L3-001 凑零钱分数 30

评论抢沙发