蓝桥杯国赛算法复习

复习内容

1.spfa
2.背包问题
3.动态规划其他常考问题
4.dfs
5.bfs
6.并查集

一、基础题回顾

1.spfa

问题描述
蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。
已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。
输入格式
第一行输入两个整数\n,m（\1≤n≤1,000,1≤m≤5,000），分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 a,b,c（1≤a,b≤n,1≤c≤200），分别代表道路的起点和道路的终点，以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。
输出格式
输出一行，输出一个整数，输出蒜头君完成比赛需要的最少时间。
样例输入
5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1
样例输出
6

题解

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e4+9;
const int M = 1e5+9;
struct edge{int u;int w;int next;edge(){}edge(int uu,int ww,int nn){u = uu;w = ww;next = nn;}
}e[N << 1];
int head[N],size;
void init(){memset(head,-1,sizeof(head));size = 0;
}
void add(int u,int v,int w){e[size] = edge(u,w,head[v]);head[v] = size++;
}
void add2(int u,int v,int w){add(u,v,w);add(v,u,w);
}
int n,m;
int dis[N];
bool vis[N];
void spfa(int u){memset(dis,0x3f,sizeof(dis));dis[u] = 0;memset(vis,false,sizeof(vis));vis[u] = true;queue<int> q;q.push(u);while(!q.empty()){u = q.front();q.pop();vis[u] = false;for(int j = head[u];~j;j = e[j].next){int v = e[j].u;int w = e[j].w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;if(!vis[v]){q.push(v);vis[v] = true;}}}}
}
int main(){init();int u,v,w;cin >>n>>m;while(m--){cin >>u>>v>>w;add2(u,v,w);}spfa(1);cout <<dis[n]<<endl;return 0;
}

2.背包问题
01背包

问题描述：
有N件物品和一个容积为M的背包。第i件物品的体积为volume[i]，价值为worth[i]。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，可以选择放或者不放。（N<=3500,M<=13000）输入格式：
第一行为物品数量N和背包容积M每行依次输入第i件物品的价值和体积样例输入：
3 103 42 66 7样例输出：
6

#include<iostream>
#include<algorithm>
using namespace std;
int dp[100][100];
int v[100],w[100];
int n,m;
int main(){cin >>n>>m;int maxs = -1;for(int i = 0;i<n;i++){cin >>v[i]>>w[i];}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(j < w[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}maxs = max(maxs,dp[i][j]);}}cout <<maxs<<endl;return 0;
}

多重背包

题目描述：
有N种物品，第i种物品的体积是c[i]，价值是w[i]，每种物品的数量都是有限的，为n[i]。现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。

#include<iostream>
#include<cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21],n[21];
int main()
{int N,V;cin>>N>>V;for(int i=1;i<=N;++i)cin>>w[i]>>c[i]>>n[i];for(int i=1;i<=N;++i){for(int j=0;j<=V;++j){for(int k=0;k<=n[i];++k){if(j>=c[i]*k)dp[i][j]=max(dp[i-1][j-c[i]*k]+w[i]*k,dp[i][j]);}}}cout<<dp[N][V]<<endl;return 0;
}

完全背包

问题描述：
当前有N种物品，第i种物品的体积是c[i]，价值是w[i]。
每种物品的数量都是无限的，可以任意选择若干件。
现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。
与01背包问题的区别就是物品有无限多个.

#include<iostream>
#include<cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21];
int main()
{int N,V;cin>>N>>V;for(int i=1;i<=N;++i)cin>>w[i]>>c[i];for(int i=1;i<=N;++i){for(int j=0;j<=V;++j){if(j>=c[i])dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]);else dp[i][j]=dp[i-1][j];}}cout<<dp[N][V]<<endl;return 0;
}

3.动态规划其他常考问题

楼梯问题
略

贪心
略

最大字段和

给定N个数A1, A2, ... An，从中选出k（k不固定）个连续的数字 Ai, Ai+1, ... Ai+k-1，使得∑i+k−1iAt 达到最大，求该最大值。

#include<iostream>
#include<algorithm>
using namespace std;
int dp[100];
int a[100];
int n;
int main(){cin >>n;int maxs = -1;for(int i = 1;i<=n;i++){cin >>a[i];dp[i] = a[i];}for(int i = 2;i<=n;i++){dp[i] = max(dp[i],dp[i-1]+a[i]);maxs = max(maxs,dp[i]);}cout <<maxs<<endl;return 0;
}

最长上升子序列

#include<iostream>
#include<algorithm>
using namespace std;
int dp[100];
int a[100];
int n;
int main(){cin >>n;int maxs = -1;for(int i = 1;i<=n;i++){cin >>a[i];}for(int i = 1;i<=n;i++){dp[i] = 1;for(int j = 1;j<=i;j++){if(a[j] < a[i]){dp[i] = max(dp[i],dp[j]+1);}}maxs = max(maxs,dp[i]);}cout <<maxs<<endl;return 0;
}

数塔问题
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
在这里插入图片描述
Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

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

Sample Output
30

#include<iostream>
#include<algorithm>
using namespace std;
int dp[100][100];
int a[100][100];
int n,m;
int main(){cin >>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin >>a[i][j];}}for(int i = 0;i<n;i++){dp[n][i] = a[n][i];}for(int i = n-1;i>1;i--){for(int j = 0;j<=i;j++){dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i];}} cout <<dp[0][0]<<endl;
}

4 dfs

问题描述n个人参加某项特殊考试。为了公平，要求任何两个认识的人不能分在同一个考场。求是少需要分几个考场才能满足条件。
输入格式第一行，一个整数n(1<n<100)，表示参加考试的人数。第二行，一个整数m，表示接下来有m行数据以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式一行一个整数，表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2+2;
int g[MAXN][MAXN];//用邻接矩阵存储关系
int room[MAXN][MAXN]; //room[i][j]表示当前i号教室第j个人为room[i][j]
int MIN ;//优化一：当前状态下的最小教室
int n,m;//点数，边数void dfs(int v,int c){if(c>=MIN)return;//剪枝if(v>n){MIN=MIN>c?c:MIN;return;}for(int i=1;i<=c;++i){//循环判断每个教室的每个人是否与v有关系int k =0;while(room[i][k]&&g[v][room[i][k]]==0){//如果当前教室i,第k个人的编号room[i][k]与v有关系退出k++;}if(room[i][k]==0){//有当前教室i的所有人无关系，可加入教室room[i][k]=v;dfs(v+1,c);//把v+1加入到教室room[i][k]=0;//回溯}}room[c+1][0]=v;//或者新开一间教室放该v,(注不是所有教室不满足条件)dfs(v+1,c+1);room[c+1][0]=0;}int main(){//相当于图的着色问题，用dfs scanf("%d%d",&n,&m);MIN = n;//易知最多教室为nint a,b;for(int i=0;i<m;++i){scanf("%d%d",&a,&b);g[a][b]=g[b][a]=1;}dfs(1,0);printf("%d",MIN);return 0;
}

A - 滑雪 POJ - 1088
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。Output
输出最长区域的长度。Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9Sample Output
25

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int mp[100][100];
int ansm = -1;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int dfs(int x,int y){int ans = -1;if(ans > 0){return ans;}ans = 1;for(int i = 0;i<4;i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] < mp[x][y]){int temp = dfs(tx,ty) + 1;ans = max(ans,temp);} }return ans; 
}
int main(){cin >>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin >>mp[i][j];}}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){int t = dfs(i,j);ansm = max(ansm,t);}}cout <<ansm<<endl;
}

5.bfs

迷宫最短路

#include<iostream>
#include<queue>
using namespace std;
struct node{int x,y,s;node(){}node(int xx,int yy,int ss){x = xx;y = yy;s = ss;}
};
int n,m;
char mp[100][100];
bool vis[100][100];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int bfs(int x,int y){queue<node> q;q.push(node(x,y,0));vis[x][y] = true;while(!q.empty()){node now = q.front();q.pop();for(int i = 0;i<4;i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] != '#'){if(mp[tx][ty] == 'T'){return now.s + 1;}else{vis[tx][ty] = true;q.push(node(tx,ty,now.s+1));}}}}
}
int main(){cin >>n>>m;for(int i = 0;i<n;i++){cin >>mp[i];}int sx,sy;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(mp[i][j] == 'S'){sx = i;sy = j;}}}cout <<bfs(sx,sy)<<endl;return 0;
}

拓展
dfs与bfs的抽象问题

例1：给定n nn个整数，要求选出K KK个数，使得选出来的K KK个数的和为s u m sumsum

#include <iostream>
using namespace std;
int a[40];
int n, k, sum, ans;
//i表示选择第i个数，cnt记录选择的个数，s表示选取数的和
void dfs(int i, int cnt, int s) {if (i == n) {if (cnt == k && s == sum) {ans++;}return;}dfs(i + 1, cnt, s); //不选该数dfs(i + 1, cnt + 1, s + a[i]); //选择该数
}
int main() {cin >> n >> k >> sum;for (int i = 0; i < n; ++i) {cin >> a[i];}ans = 0;dfs(0, 0, 0);cout << ans << endl;return 0;
}

例2：取木棍：
有4个木棍输入每个木棍长度；
判断是否可以拼成三角形：
比如 1 2 3 3可以拼成三角形：
输出yes；

#include <iostream>
using namespace std;
int n,m,sum;
int a[10010];
bool vis[10010];
bool f;
void dfs(int p,int s,int st)
{if(f){return ;}if(p==3){f=true;return ;}if(s=sum/3)//当前的边正好可以构成三角形的一个边 {dfs(p+1,0,0);return ;	}for(int i=0;i<n;++i){if(!vis[i]){vis[i]=true;dfs(p,s+a[i],i+1);vis[i]=false;}}
}
int main()
{cin>>n;for(int i=0;i<n;++i){cin>>a[i];sum+=a[i];}if(sum%3!=0)//如果不是3的倍数的话就已经明摆着不可以成功 {cout<<"no"<<endl;return 0;}else dfs(0,0,0);if(f) cout<<"yes"<<endl;else cout<<"no"<<endl;return 0; }