以下是为您整理出来关于【算法竞赛进阶指南】合集内容，如果觉得还不错，请帮忙转发推荐。
题目链接：https://www.acwing.com/video/472/给定n门课，存在先修关系，构成一个森林，修一门课之前他的先修课程一定要完成，问在选m门课的情况下最多能获得多少学分？如果没有先修规则就是一个裸的01背包问题。但这个问题不能用01背包解决。而是一个分组背包问题，设f[x,j]为x为根的子树中修j门的最大学分数，从结点x出发，子树的数量就是分组的数量，背包的容量从0-j-1，每个分组中第k个物品的体积是k。在每个点的子树处理完之后...
题目要求：给一个n*m的矩阵，求从左上角到右下角的两条路径，使得两条路径上的值只和最大。从左上角往右下角走的时候只能向下或者向右。在这个问题中阶段就是步数，步数与坐标点的横纵坐标之和相差一个常数，所以可以通过坐标只和以及两个点的横坐标来确定当前的状态集合。此时通过一个点的所有入边更新一个点即可。一共有四种状态，代价可以先计算出来。其中坐标枚举的范围要综合考虑横纵坐标的范围。代码：#include<iostream> #i...
题目链接：https://www.acwing.com/problem/content/276/题目给出m个地点，n个任务，每两个地点之间有距离，有三个服务员，初始时刻服务员在1,2,3位置，每个服务必须且只有一个人到指定的地点，问完成这些服务的最小移动距离之和，决策集合是所有完成了i个任务并且另外两个人在x,y位置的方案，属性是距离之和的最小值，在DP中有两种常见的更新方式，分别是通过依赖的状态来更新当前的状态和通过当前的状态去更新以来的状态本问题中...
《算法竞赛进阶指南》 二分篇 学习1二分的原理其实很简单整数集合上的二分复习一下c++ STL库 lower_bound upper_bound :利用二分查找的方法在一个排好序的数组中进行查找 lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound( begin,end,num)：从数组的beg...
题目链接：https://www.acwing.com/problem/content/246/线段树合并线段的时候要更新结点中的ans值，但是这个值的更新依赖于lmax与rmax，这两个值的更新又依赖于sum，故查询的时候需要返回的是一个结点，返回代表的区间的信息。代码：#include<iostream> #include<cstdio> usingnamespace std; constint maxn = 500010; constint inf=0x3f3f3f3f; int n,m; struct node{int l,r,s,lx,rx,ans; }t[maxn*4]; void pushup(int rt){t[rt...
题目链接：https://www.acwing.com/problem/content/199/分解N！的质因数，因为N!的质因数不超过N，所以可以先预处理出[1,N]的质数，然后就是简单的求和计算了。筛法采用的是优化之后的艾式筛法的优化了，算法的时间复杂度是O(n*loglogn)，十分接近线性。代码：#include<iostream> #include<vector> #include<cstring> usingnamespace std; #define maxn 1000010 vector<int>primes; bool v[maxn]; void get_primes(int n){memset...
题目链接：https://www.acwing.com/problem/content/description/151/给定长度为n的序列，代表一个单词的出现次数，要求构造k叉哈夫曼树使得总权值最小，并且在权值最小的情况下问最小的高度是多少？我们可以考虑不断取k个数组成一个新的结点放入优先队列，但是根节点可能不满k叉，所以可以考虑在其中不超过k-1个零来上调权值比较大的结点，权值为零的结点肯定在最深层的一个父节点上。也只有这一个父节点是不满k叉的，这个可以通过...
题目链接：http://poj.org/problem?id=3635题目和最短路算法的形式很像，只要对每个状态确定转移的分支即可，其中每次油量只加一，因为后续一定会在队列中被取出来重新加一（如果可以的话）代码：#include<iostream> #include<cstring> #include<queue> usingnamespace std; #define maxn 1005 int head[maxn],nxt[maxn*20+10],ver[maxn*20+10],len[maxn*20+10]; int d[maxn][105]; int n,m,q; bool vis[maxn][105]; int price[max...
题目链接：https://www.acwing.com/problem/content/149/题目中给出一些点在x轴上的位置，问选出k对位置的情况下，他们的两两距离之和的最小值是多少？容易直到，选中的位置一定是相邻的而且没有交集，我们对原始序列求差分之后问题就变成了在这个差分序列中寻找k个不相邻的数，使得和最小。当选中了其中的k个两两间隔为1的位置之后，如果下一次从剩下的区间里面选出一个最小的区间跟这k个点相邻就破坏了性质，这k个点一定会被周围...
题目链接：http://poj.org/problem?id=1190剪枝的常用思考策略：优化搜索顺序（从决策数量越少的位置开始决策）、排除冗余的等效的操作、可行性剪枝、最优性剪枝、上下界剪枝，其中在可行性剪枝方面可以利用“未来期望进行剪枝”要充分利用不等式关系进行放缩，将不可能的状态进行剪枝，也是一个对“未来状态的估计”。代码：#include<iostream> #include<cstdio> #include<math.h> usingnamespace std; #define maxn 25 constint ...