题目链接注意：公共子串是要求连续的，公共子序列可以不连续 #include<stdio.h> #include<algorithm> #include<string> using namespace std; short dp[10002][10002]; int main(){ char s1[10001], s2[10001]; scanf("%s%s", s1, s2); int m = strlen(s1); int n = strlen(s2); short maxcnt = 0; for (int i = 0; i <=...

练习动态规划，思路：dp[i][j]:表示是s1的前缀长度为i，s2的前缀长度为j时的最长公共子序列长度（不要求连续）1.边界初始化：s1的前缀长度为0，或s2的前缀长度为0时,最长公共子序列长度是02.小问题向大问题转移：若s1和s2的上一次对比元素相等，则在这次的dp值+1；若不等，则取两者相比较的最大值（最长的公共前缀值）为这次的dp值。注意点：即使当前字符并不相等，也要看看保留哪个字符，可以使得当前两个字符串（其实是长度为0到i前缀子串）公共子序列更长。 #include<stdio.h> #include<algorithm> #include<stri...

动态规划的入门练习 #include<stdio.h> #include<vector> using namespace std; int main() { int m, n; while (scanf("%d%d", &m, &n) != EOF) { //初始化dp vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); //0个苹果，n个盘子，只有1种分法 for (int i = 0; i <= n; i++) { dp[0][i] ...

题目链接思路：考察单源最短路径，用Dijkstra算法：BFS遍历+贪心算法1.先定义距离数组，记录所有点到起点的距离，初始正无穷2.BFS：取出起点，（如果更小）更新邻居到起点的距离(利用小根堆--优先队列结构实现）3.贪心：取出离结点最近的点，设为新起点，执行2 #include<stdio.h> #include<vector> #include<queue> using namespace std; struct Edge { int u; int v; int w; Edge(int u_, int v_, int w_) { u = u_; v ...

思路：构造最小生成树，即保证所有顶点连通（间接也可以）+边的权值最小。可用克鲁斯克拉算法求生成树：每次选权值最小的边，判断若边所在的两个顶点不连通则加入树中，否则跳过该边，一直到树构建完成（特征是边数=顶点个数-1）。 #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; //初始化 void Initfun(int n) { for (int i = 1; i < n;...

题目链接思路：依次把输入结点-结点加入集合中（形成1棵树），判断是否标记false：（注意是仅标记，非立即终止树的构造）1.有环不行：用并查集判断，在已连通的2顶点（处于同一集合，根一样），加入一条边则成环2.多个入边不行：用一个数组记录各个顶点入度3.不相连不行：无环的连通性：边数=结点个数-1ps：呜呜呜呜呜呜我以后一定认真写if-else，搞了半天没accepted，逻辑检查了几遍发现是main里面第二个if后面没写else，导致本来else中的代码也默认执行了！ #include<stdio.h> #include<vector> #include<alg...

思路：考察并查集的基本操作，根据题目要求构建并查集，初始化并查集个数为城镇个数，依次输入道路合并，最后需要建设的道路数目为并查集个数-1：合并到最后只有1个并查集，则说明集合内结点相互连通，不用建路；合并到最后只有2个并查集，之间要建1条路才连通；合并到最后只有3个并查集，之间要建2条路才连通； #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; int setCnt;//记...

题目链接题目:把含若干数字的数组任意划分成两个子数组，使得两个子数组的和相差最小。本题采用3种解法，最后一种ac。解法一：动态规划（数组和不大时可以采用，否则容易超时）思路：设数组总和为sum，目标是找到一个子数组使得子数组和尽可能<=sum/2，这样两个数组和若相等，则和相差最小是0。对于每一个数组中数字，都要更新dp数组：如果之前能凑出vec[i](数组元素），那么现在有了j，你就能凑出vev[i]+j了（前提是 vev[i]+j 不超过 target） #include<stdio.h> #include<vector> #include<algori...

8皇后问题：将8 个皇后放置在8*8的棋盘上，并且使得皇后彼此之间不能攻击。皇后彼此不能相互攻击：指的是任何两个皇后都不能处于同一条横线、纵线或者斜线上。返回解决方案个数。思路：逐行放置皇后，每次尝试将皇后放在当前一行的某一列，判断是否不互相攻击，，冲突则跳过该列；如果不冲突就在该列放置皇后，并且递归处理下一个位置的皇后，最后注意撤销当前选择的列，以便尝试其他可能的列。 #include<stdio.h> #include<vector> using namespace std; vector<vector<int>> queeenVec;//结...

思路：采用广度优先遍历，每次从队列头拿出一个字符串，检查，然后生成所有可能的“下一代”字符串放回队列尾部这样，先入队的（移动步数少的）一定会先被处理，保证了找到的第一个解就是步数最少的解。存放待处理的字符串——队列；找子串——find；记录哪些字符串已经处理过了（防止走回头路，比如从 A 变到 B，又从 B 变回 A）——map； #include<iostream> #include<queue> #include<unordered_map>//时间效率为o(1)，比map高 #include<string> using namespace ...

题目链接通过广度优先搜索（BFS）来求解树的高度，其核心思想是将“求树的高度”转化为“求根节点到所有其他节点的最大距离”。 #include<stdio.h> #include<string> #include<queue> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m);//输入结点个数，根结点编号 //用邻接表存储边和结点，邻接表的本质是二维数组 vector<vector<int>>tree(n + 1);//...

题目链接要求输出哈夫曼树的带权路径长度，优先队列默认是大根堆排序，若元素取反存入就是小根堆存储，每次取出最小的两个数相加，结果再存入优先队列比较，直到队列中仅剩一个元素，即为wpl的相反数。 #include<stdio.h> #include<string> #include<queue> using namespace std; int main() { int N,data; priority_queue<int> myqueue; scanf("%d", &N); for (int i = 0; i < ...

优先队列：默认大根堆，重载运算符的比较规则有点绕 #include<stdio.h> #include<string> #include<queue> using namespace std; struct Complex { int a; int b; Complex(int a_, int b_) { a = a_; b = b_; } }; //因为默认的比较规则只能比较int和double类型，故自定义运算符，重载 < 号 //注意：(a<b)为真或(a>b)为真,都是a（左边那个）输了，谁被判定为输（返回 true），谁就要被挤到...

按题目要求改写比较规则，利用sort排序动态数组 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; //修改比较规则 bool compare(int l,int r){ //不交换的情况返回真 //奇数在前偶数在后不交换 //奇数l>奇数r不交换 //偶数l<偶数r不交换 if((l%2!=0)&&(r%2==0)){ return true; }else if((l%2!=0)&&(r%2!=0)&&a...