算法训练1
01背包问题
背包状态方程----动态规划
二维dp
使用 f[i][j] = max(f[i-1][j] ,f[i-1][j - w[i]] + v[i]);
伪代码：
int dp[100][100];
void test6() {int n; //装备数量int m; //背包容量int v[105], w[105]; //前面空间，后面价值for (int i = 1; i <= n; i++) {for (int j = m; j >= 0; j--) {if (j >= v[i]) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}else {dp[i][j] = dp[i - 1][j];}}}
}其中，dp中的横坐标i代表的是第i个装备，纵坐标 j 为背包容量，由于这里dp一直记录的是最大的，所以可以优化为一维dp
同理的一道题：
使用一维dp，注意的是：进行更新 f[ ]时，要从后面开始更新，这样可以使用的f[j - v[i]] 全是上次草药的值，如果从小往大进行更新，会导致后面更新，装两次一样的草药。导致错误。
void test3() {int timeAll, num;scanf("%d%d", &timeAll, &num);int v[105],w[105];int f[1005];for (int i = 1; i <= num; i++) {scanf("%d %d", &v[i], &w[i]);}for (int i = 0; i <= timeAll; i++) {f[i] = 0;}for (int i = 1; i <= num; i++) {for (int j = timeAll; j >= 0; j--) {if (j >= v[i]) {f[j] = max(f[j], f[j - v[i]] + w[i]);}else {f[j] = f[j];}}}printf("%d", f[timeAll]);
}桶排序+暴力处理
这里就不断处理最大值，最大湿度衣服进行烘干，然后暴力执行。
//堆排序
int f[500005];
void test5() {int n, a, b;scanf("%d%d%d", &n, &a, &b);int max = 0, sum = 0,time = 0;for (int i = 1; i <= n; i++) {int k;scanf("%d", &k);f[k]++;if (k > max) {max = k;}}while (1) {if (max <= sum) {break;}f[max]--;if (max > b) {f[max - b] += 1;}while(f[max] == 0) {max--;}sum += a;time += 1;}printf("%d", time);}
二分答案：
题解 P2678 【跳石头】 - 洛谷专栏 (luogu.com.cn)
https://www.luogu.com.cn/article/08mxthsv
运用二分答案，进行枚举判断答案是否正确
比如：
使用check函数检查答案是否正确，运用二分答案：两个要素
单调性，有界性。答案可以枚举出来
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
int H[1000005];
int N, M;
bool check2(int l) {int count = 0;for (int i = 1; i <= N; i++) {if (H[i] > l) {count += H[i] - l;if (count >= M) {return true;}}}return false;
}int max(int a, int b) {return a > b ? a : b;
}void test8() {scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) {scanf("%d", &H[i]);}sort(H + 1, H + 1 + N);int left = 1, right = H[N], ans = 0;while (left <= right) {int mid = (left + right) / 2;if (check2(mid)) {ans = max(ans, mid);left = mid + 1;}else {right = mid - 1;}}cout << ans;}
int main() {test8();
}还有这题：P1824 进击的奶牛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
同理：使用二分答案，解决
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int V[200005];
int N, C, H;
using namespace std;
int check(int k) {int last = V[1], count = 0;for (int i = 2; i <= N; i++) {if (V[i] - last < k) {count++;if (H < count)return 1;}else {last = V[i];}}return 0;
}int max(int a, int b) {return a > b ? a : b;
}void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}void test7() {scanf("%d %d", &N, &C);for (int i = 1; i <= N; i++) {scanf("%d", &V[i]);}H = N - C;sort(V+1,V+N+1);int left = 1, right = V[N], ans = 0;while (left <= right) {int mid = (left + right) / 2;if (check(mid) == 0) {ans = max(mid, ans);left = mid + 1;}else {right = mid - 1;}}printf("%d", ans);}
int main() {test7();
}并查集
比如：
P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
找祖先，就一直找到最初的组件，判断是否相等，如果相等，就说明这两个是在同一个集合中。
int find(int x) {while (x != f[x]) {x = f[x];}return x;
}//路径压缩，循环实现
int find(int x){while (x != f[x]){f[x] = f[f[x]];x = f[x]}return x;
}//路径压缩，递归实现
int find(int x){if(x == f[x])return x;return f[x] = find[f[x]];
}路径压缩后会可以使查询祖先时，快不少。
并查集还有一个重要的出来查询之外，还有合并了
这里可以直接把一个元素的祖先赋值给一个元素的祖先
void merge(int a,int b){int a1 = find(a);int a2 = find(b);f[a1] = a2;
}
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
int N, M;
int f[10005];
void init() {for (int i = 1; i <= N; i++) {f[i] = i;}
}int find(int x) {while (x != f[x]) {f[x] = f[f[x]];x = f[x];}return x;
}void test8() {cin >> N >> M;init();for (int i = 1; i <= M; i++) {int z, x, y;cin >> z >> x >> y;if (z == 1) {f[find(x)] = find(y);}else if (z == 2) {if (find(x) == find(y)) {cout << "Y\n";}else {cout << "N\n";}}}}
int main() {test8();
}最小生成树
算法：prim,kruskal算法
主要学习了kruskal算法
运用到了并查集。P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
顺便学习了c++中sort函数，自定义排序方式，
图中的边权值，进行排序。
kruskal:先找出最小没有连接的边，然后判断如果连接后有没有回路，如果有回路，就舍弃这条边，没有就把这条边加入，然后再进行判断下一条边。
P1195 口袋的天空 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类似的，这个是需要把n个点构造成k棵最小生成树，所以只要加入的边等于n-k就行了
附上代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int N, M, K;
int f[1005];struct edge {int v, u, w;
}edges[10005];int find(int x) {while (f[x] != x) {f[x] = f[f[x]];x = f[x];}return x;
}
bool cmp(edge a, edge b) {return a.w < b.w;
}void kruskal() {int ans = 0, cnt = 0;sort(edges + 1, edges + M + 1, cmp);for (int i = 1; i <= M; i++) {int a1 = find(edges[i].u);int a2 = find(edges[i].v);if (a1 == a2) {continue;}ans += edges[i].w;f[a1] = a2; //连接两个顶点cnt++;if (cnt == N - K) {cout << ans;return;}}cout << "No Answer";
}void test() {cin >> N >> M >> K;for (int i = 1; i <= N; i++) {f[i] = i;}for (int i = 1; i <= M; i++) {cin >> edges[i].u >> edges[i].v >> edges[i].w;}kruskal();
}
int main() {test();
}最短路径
dijkstra算法+链式前向星存边，
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <algorithm>
#include<cstring>
#define inf 2147483647
using namespace std;
long long dis[10005];
bool vis[10005];
int head[10005];
int n, m, s,cnt = 0;
//在这里head数组储存i点的一条边的编号，edge中的next表示的是起点相同的边的编号，
//可以从加边那里深刻理解
//链式前向星存边
struct edge {int next;int to;int val;
}edges[500005];void dijkstra() {dis[s] = 0;int cur = s;while (!vis[cur]) {vis[cur] = true;for (int i = head[cur]; i != 0; i = edges[i].next) {if (!vis[edges[i].to] && dis[edges[i].to] > dis[cur] + edges[i].val) {dis[edges[i].to] = dis[cur] + edges[i].val;}}int min = inf;for (int i = 1; i <= n; i++) {if (!vis[i] && min > dis[i]) {min = dis[i];cur = i;}}}for (int i = 1; i <= n; i++) {cout << dis[i] <<" ";}
}//加边
void add(int a,int b,int c) {edges[++cnt].next = head[a];edges[cnt].to = b;edges[cnt].val = c;head[a] = cnt; //记录编号
}void test() {cin >> n >> m >> s;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}for (int i = 1; i <= n; i++) {dis[i] = inf;}dijkstra();
}int main() {test();
}训练总结：昨天晚上加今天一天完成了这所有的训练，确实收获不少。
靠思维，暴力解决：A,,K,L
动态规划还是不太熟练， B
二分答案，能够理解。 C,D,E,F
并查集：G,H
最小生成树：H,I
最短路径：J
思路有个大概，但是完全自己想出来，还是有点难度