文章目录
Kruskal算法：最小生成树
题目背景故事
你是一名建筑工人，负责在一个城市中建造一座桥。你需要把这座桥连接的两个岸边的点连起来，并且要使得连接的边的权值和最小。
题目描述
给定一张带权的无向图，求出其最小生成树。
输入描述
第一行包含两个整数n和m，分别表示点数和边数。
接下来m行，每行包含三个整数u, v, w，表示一条从点u到点v的有向边，权值为w。
输出描述
输出最小生成树的权值和。
输入样例
4 5
1 2 3
1 3 4
4 2 6
4 3 5
2 3 7
输出样例
14
解题思路
这道题我们可以使用Kruskal算法来解决。Kruskal算法是一种用于求解最小生成树的算法，它的核心思想是将图中所有边按照权值从小到大排序，然后依次加入边，如果加入后不会形成环，就加入这条为了判断一条边是否会形成环，我们可以使用并查集来维护连通性。每次加入一条边时，我们先将两个端点所在的集合合并，然后判断两个端点是否在同一个集合中，如果不是，就加入这条边。
C++代码
#include<iostream>#include<algorithm>#include<cstring>usingnamespace std;constint N =1010;structEdge{int u, v, w;} edges[N];int p[N];intfind(int x){if(p[x]!= x) p[x]=find(p[x]);return p[x];}intmain(){int n, m;
cin >> n >> m;for(int i =0; i < m; i ++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;for(int i =1; i <= n; i ++) p[i]= i;sort(edges, edges + m,[](Edge a, Edge b){return a.w < b.w;});int res =0;for(int i =0; i < m; i ++){int u = edges[i].u, v = edges[i].v;int t1 =find(u), t2 =find(v);if(t1 != t2){
p[t1]= t2;
res += edges[i].w;}}
cout << res << endl;return0;}
动态规划：最长公共子序列
题目背景故事
你是一名研究生，正在研究两个DNA序列的相似性。你需要找出这两个DNA序列的最长公共子序列，并确定它们的相似度。
题目描述
给定两个字符串A和B，求出它们的最长公共子序列的长度。
输入描述
第一行包含两个字符串A和B。
输出描述
输出最长公共子序列的长度。
输入样例
abcde
abcdf
输出样例
4
解题思路
这道题我们可以使用动态规划来解决。我们可以定义一个二维数组dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。
对于每一个dp[i][j]，我们可以由dp[i-1][j]和dp[i][j-1]转移而来，但是如果A[i]==B[j]，我们就可以加上dp[i-1][j-1]的值。
状态转移方程如下：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
)
dp[i][j]=\max(dp[i-1][j],dp[i][j-1])
dp[i][j]=max(dp[i−1][j],dp[i][j−1])
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
−
1
]
+
1
(
A
[
i
]
=
=
B
[
j
]
)
dp[i][j]=dp[i-1][j-1]+1(A[i]==B[j])
dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])
C++代码
#include<iostream>#include<cstring>usingnamespace std;constint N =1010;char A[N], B[N];int dp[N][N];intmain(){
cin >> A +1>> B +1;int n =strlen(A +1), m =strlen(B +1);for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++){
dp[i][j]=max(dp[i-1][j], dp[i][j-1]);if(A[i]== B[j]) dp[i][j]= dp[i-1][j-1]+1;}
cout << dp[n][m]<< endl;return0;}
动态规划+二分：最小表示法
题目背景故事
你是一名研究生，正在研究两个DNA序列的相似性。你需要找出这两个DNA序列的最长公共子序列，并确定它们的相似度。
题目描述
给定两个字符串A和B，求出它们的最长公共子序列的长度。
输入描述
第一行包含两个字符串A和B。
输出描述
输出最长公共子序列的长度。
输入样例
abcde
abcdf
输出样例
4
解题思路
这道题我们可以使用动态规划来解决。我们可以定义一个二维数组dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。
对于每一个dp[i][j]，我们可以由dp[i-1][j]和dp[i][j-1]转移而来，但是如果A[i]==B[j]，我们就可以加上dp[i-1][j-1]的值。
状态转移方程如下：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
)
dp[i][j]=\max(dp[i-1][j],dp[i][j-1])
dp[i][j]=max(dp[i−1][j],dp[i][j−1])
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
−
1
]
+
1
(
A
[
i
]
=
=
B
[
j
]
)
dp[i][j]=dp[i-1][j-1]+1(A[i]==B[j])
dp[i][j]=dp[i−1][j−1]+1(A[i]==B[j])
C++代码
#include<iostream>#include<cstring>usingnamespace std;constint N =1010;char A[N], B[N];int dp[N][N];intmain(){
cin >> A +1>> B +1;int n =strlen(A +1), m =strlen(B +1);for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++){
dp[i][j]=max(dp[i-1][j], dp[i][j-1]);if(A[i]== B[j]) dp[i][j]= dp[i-1][j-1]+1;}
cout << dp[n][m]<< endl;return0;}
动态规划+二分：最小表示法
题目背景
有一种古老的文字，是由一些简单的符号构成的。每个符号有一个价值，从左到右依次给出。你的任务是将这些符号解码成一个数字，其中任意两个相邻的符号的价值的最小值不超过9。
题目描述
给定一个由
n
n
n 个符号组成的序列，每个符号的价值为
a
i
a_i
ai，你的任务是将这些符号解码成一个数字。其中任意两个相邻的符号的价值的最小值不超过
9
9
9。
输入描述
第一行包含一个整数
n
n
n，表示符号的个数。
第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \dots, a_n
a1,a2,…,an，表示每个符号的价值。
输出描述
输出一个数字，表示解码后的数字。
输入样例
5
1 2 3 4 5
输出样例
12345
解题思路
可以使用动态规划来解决这个问题。定义状态
d
p
i
dp_i
dpi 表示前
i
i
i 个符号的最小表示法。
使用二分的方法来枚举任意两个相邻的符号的价值的最小值的范围。对于每一个符号
a
i
a_i
ai，我们可以在
[
1
,
9
]
[1,9]
[1,9] 之间二分查找最小的
k
k
k，使得
k
+
d
p
i
−
1
k+dp_{i-1}
k+dpi−1 能够表示
a
i
a_i
ai。
C++代码
#include<iostream>#include<cstring>usingnamespace std;constint N =100010;int n;int a[N];int dp[N];intmain(){
cin >> n;for(int i =1; i <= n; i ++) cin >> a[i];memset(dp,0x3f,sizeof dp);
dp[0]=0;for(int i =1; i <= n; i ++){int l =1, r =9;while(l < r){int mid = l + r >>1;if(a[i]- dp[i-1]< mid) r = mid;else l = mid +1;}
dp[i]=min(dp[i], dp[i-1]+ l);}
cout << dp[n]<< endl;return0;}
动态规划+贪心：最小代价带权图的最大点双
题目背景
在一张带权无向图中，你需要选择一个最大的点双使得它的代价最小。
你的任务是计算出这个最小代价。
题目描述
给定一张
n
n
n 个节点、
m
m
m 条边的带权无向图，边权为正整数。
你的任务是选择一个最大的点双使得它的代价最小。
输入描述
第一行包含两个整数
n
,
m
n, m
n,m，表示节点数和边数。
接下来
m
m
m 行，每行包含三个整数
u
,
v
,
w
u, v, w
u,v,w，表示一条从节点
u
u
u 到节点
v
v
v，权值为
w
w
w 的有向边。
输出描述
输出一个整数，表示选择一个最大的点双使得它的代价最小的最小代价。
输入样例
4 5
1 2 3
2 3 4
3 4 5
4 1 6
1 3 7
输出样例
7
解题思路
定义状态
d
p
i
,
S
dp_{i,S}
dpi,S 表示当前已经选择了集合
S
S
S 中的节点，且最后一个选择的节点为
i
i
i 时的最小代价。
我们可以使用贪心的思想来枚举下一个要选择的节点。
对于每一个点
i
i
i，我们可以遍历所有与之相连的点
j
j
j，更新状态
d
p
j
,
S
∪
j
=
min
(
d
p
j
,
S
∪
j
,
d
p
i
,
S
+
w
i
,
j
)
dp_{j,S\cup{j}}=\min(dp_{j,S\cup{j}},dp_{i,S}+w_{i,j})
dpj,S∪j=min(dpj,S∪j,dpi,S+wi,j)
最终，我们只需要枚举所有的点
i
i
i，找出
d
p
i
,
1
,
2
,
.
.
.
,
n
dp_{i,{1,2,...,n}}
dpi,1,2,...,n 的最小值即可。
C++代码
#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =210;constint M = N * N;constint INF =0x3f3f3f3f;int h[N], e[M], ne[M], w[M], idx;int n, m;int f[N][N];voidadd(int a,int b,int c){
e[idx]= b, w[idx]= c, ne[idx]= h[a], h[a]= idx ++;}voidfloyd(){memset(f,0x3f,sizeof f);for(int i =1; i <= n; i ++) f[i][i]=0;for(int k =1; k <= n; k ++)for(int i =1; i <= n; i ++)for(int j =1; j <= n; j ++)
f[i][j]=min(f[i][j], f[i][k]+ f[k][j]);}intmain(){
cin >> n >> m;while(m --){int a, b, c;
cin >> a >> b >> c;add(a, b, c);
f[a][b]=min(f[a][b], c);}floyd();int res = INF;for(int i =1; i <= n; i ++)
res =min(res, f[i][i]);
cout << res << endl;return0;}
贪心+二分：最大子矩形
题目背景
你有一个矩形，你需要找到最大的子矩形使得它的面积最小。
你的任务是计算出这个最小的面积。
题目描述
给定一个
n
n
n 行
m
m
m 列的矩阵，每个位置的值为
0
0
0 或
1
1
1。
你的任务是找到一个最大的子矩形使得它的面积最小。
输入描述
第一行包含两个整数
n
,
m
n, m
n,m，表示矩阵的行数和列数。
接下来
n
n
n 行，每行包含
m
m
m 个整数，表示矩阵的值。
输出描述
输出一个整数，表示找到一个最大的子矩形使得它的面积最小的最小面积。
输入样例
4 5
1 0 1 1 0
1 0 1 1 0
1 1 1 1 1
0 0 1 1 1
输出样例
4
解题思路
定义状态
d
p
i
,
j
dp_{i,j}
dpi,j 表示当前位置在
(
i
,
j
)
(i,j)
(i,j)，最大子矩形的最小面积。
使用二分的方法来枚举当前的矩形的高度
h
h
h。对于每一个位置
(
i
,
j
)
(i,j)
(i,j)，在
[
0
,
n
]
[0,n]
[0,n] 之间二分查找最小的
h
h
h，使得以
(
i
,
j
)
(i,j)
(i,j) 为左上角，高度为
h
h
h 的矩形能够被覆盖。
C++代码
#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =110;int n, m;int a[N][N];int h[N][N];int l[N], r[N];int st[N], top;intmain(){
cin >> n >> m;for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++)
cin >> a[i][j];for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++){if(!a[i][j]) h[i][j]=0;else h[i][j]= h[i-1][j]+1;}int res =0;for(int i =1; i <= n; i ++){
top =0;for(int j =1; j <= m; j ++){while(top && h[i][st[top]]>= h[i][j]) top --;
l[j]= st[top];
st[++ top]= j;}
top =0;for(int j = m; j; j --){while(top && h[i][st[top]]>= h[i][j]) top --;
r[j]= st[top];
st[++ top]= j;}for(int j =1; j <= m; j ++)
res =max(res,(r[j]- l[j]+1)* h[i][j]);}
cout<< res << endl;return0;}
贪心+二分：滑动窗口最大值
题目背景
你有一个长度为
n
n
n 的数组，你需要找到长度为
k
k
k 的滑动窗口中的最大值。
你的任务是在给定的数组中找到所有的滑动窗口的最大值。
题目描述
给定一个数组
a
a
a 和一个整数
k
k
k，你的任务是找到所有长度为
k
k
k 的滑动窗口中的最大值。
输入描述
第一行包含两个整数
n
,
k
n, k
n,k，表示数组的长度和滑动窗口的长度。
第二行包含
n
n
n 个整数，表示数组的值。
输出描述
输出一个整数，表示找到的所有滑动窗口的最大值。
输入样例
10 3
2 3 4 2 5 6 7 8 1 2
输出样例
4 4 4 5 5 6 7 8 8 8
解题思路
用贪心的思想来解决这个问题。
定义状态
d
p
i
dp_i
dpi 表示当前位置在
i
i
i，滑动窗口的最大值。
我们可以使用二分的方法来枚举当前的滑动窗口的左端点
l
l
l。对于每一个位置
i
i
i，我们可以在
[
i
−
k
+
1
,
i
]
[i-k+1,i]
[i−k+1,i] 之间二分查找最小的
l
l
l，使得
[
l
,
i
]
[l,i]
[l,i] 之间的所有数的最大值是
a
i
a_i
ai。
#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =1e5+10;int n, k;int a[N];intmain(){
cin >> n >> k;for(int i =1; i <= n; i ++) cin >> a[i];for(int i =1; i <= n; i ++){int l = i - k +1, r = i;while(l < r){int mid = l + r >>1;if(a[mid]< a[i]) l = mid +1;else r = mid;}
cout << a[l]<<" ";}return0;}
版权归原作者 生产队的小刘 所有， 如有侵权，请联系我们删除。