最小点覆盖 (Minimum Vertex Cover, MVC)  用最少数量的顶点覆盖图中所有的边。  最小边覆盖 (Minimum Edge Cover, MEC)  用最少数量的边覆盖图中所有的顶点。  最小支配集 (Minimum Dominating Set, MDS)  用最少数量的顶点支配图中所有的顶点。  注意  注意区分最小点覆盖和最小支配集，两者一个考虑点一个考虑边 对于A-B-C-D-E-F，最小点覆盖是3，最小支配集是2

最小支配集  选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点  题意  给定一颗n个结点的树，求最小支配集  思路  考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：   自己： 父亲： 儿子： 对于自己和父亲，状态方程很显然可以推出，对于被儿子支配的情况，所有儿子不能依靠父亲，只能靠自己或者靠儿子的儿子，但是，总归有一个儿子需要靠自己，不然就无法覆盖父亲，所以，维护，如果最终结果大于0,说明全都靠的儿子的儿子，需要补上一个靠儿子和自己的差值inc 对于inc，如果小于0，说明一定有一个被选了，不用再依靠inc，所以每次inc>...

最小点覆盖  选择一个点，覆盖所有相邻边，最少选几个点能覆盖所有边  题意  给定一棵n个结点的树，选定一个结点后即可覆盖他的所有邻边，求覆盖所有邻边的最少选定结点数  思路  动态规划 对于每一个结点，由于覆盖边，所以自己考虑选和不选两种情况，且父亲没选，自己就一定得选，父亲选了，自己就可选可不选，注意区分最小点覆盖，最小边覆盖，最小支配集      代码 #include<bits/stdc++.h> using namespace std; /** * dp[i][0/1];表示自己不选，自己选 * dp[i][1]=sum(min(dp[u][0],dp[u][1])+1;...

题意  对于一棵树，我们希望找到一个点，使得删除这个点之后，最大子树的结点数最小 以边的形式输入，输出被删除的点的编号和删除后最大子树的结点数  思路  考虑用无根树描述，对于树的某一个结点，删掉后，整棵树变为两部分  这个结点的父亲所属的树 这个结点的若干子树   故另表示删除这个点后最大子树结点数，表示这个点除了父亲以外的子树的总结点数，则就是祖先部分的结点数 得到,u是i的每一个儿子， 所求答案为所有中最小的一个  代码 #include<bits/stdc++.h> #define maxn 1024 using namespace std; int n; int tol[...

题意  给定一颗n个结点的树，结点编号1~n，每个结点有权值，一个点选择以后，它的父亲就不可以被选，输出能选出的最大权值  思路  对于每个点，都有选和不选两种情况，当一个点选的时候，所有的儿子都不能选，当一个点不选的时候，每个儿子取选和不选的最大值即可，维护一个二维dp数组，状态转移方程如下  注意到，由于涉及父子关系，所以考虑用有根树来维护，因为输入的时候每个除了根以外的结点都只出现一次，根不出现，所以用编号和不断减去结点编号，最终剩余的就是根 当然，本题也可以使用无根树来维护  代码 #include<bits/stdc++.h> //有根树 using namespace ...

比赛地址 A 小红的签到题 题意  输入一个大于等于三的整数n 输出一个长为n的由"_"分为两段的字符串  思路  直接硬输出即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; cout << "a_"; for(int i=2;i<n;i++){ cout << 'a'; } cout << endl; return 0; }  B 小红的模拟题 题意  读入一张n*m的地图，其中有且仅有一个陷阱，输出一条从(1,1)...

题意  共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏  思路  本题应该使用dfs+剪枝是更好写的 dp  对于0~30000这个范围，从1开始走，最大的偏移量不超过300 即相较于第一步d，最后一步的步长一定在d-300~d+300之间 对于每一步，都有可能从任何一个偏移量的步数走来，需要维护一个二维dp数组  上一步走了j走到第i座岛屿能拿到的最多宝藏，是从上上步走了j+1，j，j-1走到i-j的最大宝藏数+i处的宝藏数 由于数组不方便开负的，所以要把所有的偏移量加上一个base...

题意  给定桥的长度L，每一步可以走S~T中任意距离，桥上共有M颗石子，求走过桥最少踩多少石子 0<= L <=1e9, 1<=S<=T<=10, 1<=M<=100  思路  一个类似于走楼梯的动态规划，很显然的可以得到转移方程:其中，S<=j<=T，0<=i<=L 但是，由于L的范围很大，不可能开下这么大的dp数组，所以需要对长度进行压缩 参考NOIP2017|小凯的疑惑，数字a，b不能表示的最大数是 因为最大步长为10，所以所有超过71的数都可以等价的压缩成72 完成路径压缩后即可正常处理，对于L由于不要求恰好过桥，所以i...

题意  有若干导弹，拦截系统只能拦高度降序的一组导弹，问一套系统最多拦截多少导弹，拦截全部导弹需要几套系统  思路   对于第一个问题，直接对整个序列跑一个最长递减子序列(LDS Longest-Decreasing-Subsequence)   对于第二个问题，正解是跑一个最长递增子序列(LIS)   对于第二个问题，证明如下 记程度n 首先，至少需要n套系统，是显然可以得到的 需要证明的是，至多也只需要n套系统，由Dilworth定理可得，一个序列的最少不上升子序列数目就是其LDS长度   AC代码 #include<bits/stdc++.h> using namespace...

题意  有n个区间，从每个区间中取一个值求 的种数  思路  分组背包，考虑前i组能不能凑出j，，其中k属于a[i] 双层枚举i,j,对于每一个j枚举区间，O(100*1000000*100)=O(1e10),过不了一点   for(int i=1;i<=n;i++){ for(int j=1;j<1e6;j++){ for(int k=a[i].first;k<=a[i].second;k++){ dp[i][j]=dp[i-1][j-k*k] } } }   使用bitset优化  bitset   定义：bitset<大小>   方法： count():返回...

题意  共有n个人，每个人有身高，移除若干人，使得序列为{纯升序||纯降序||先升序后降序}，求最少的移除人数  思路  方法1：对于整个序列正着求一个最长上升子序列，反着求一个最长上升子序列，枚举每个位置两个序列和，最大的减一即为序列最长长度。 方法2：维护一个二维dp数组，第二维记录当前元素属于升序列还是降序列，对于每个位置，如果他的值大于前面的某个值，则维护升序列，如果他的值小于，则维护降序列，特别的，维护降序列的时候，要比较作为降序列的开始还是衔接在前一个降序列，取两种情况中的最优解。 初值：对于每一个元素，至少都可以自己作为一个序列，所以所有初值为1。  PS  对于第二种方法，不需...

题意  给定n堆石子，成环放置，每堆石子有自己的重量，每次合并可以合并相邻的两堆，合并的得分是两堆石子重量和，求解把所有石子合并成一堆所得的最大得分和最小得分  思路  由于两堆石子是相邻的，所以每一次合成其实是对一个区间中的两堆的分界做考虑，下面按求最大得分考虑，如一共1~5，合并1~5的最后一次等价于将1~5拆分成两堆的不同分界的不同价值{[1|2,3,4,5],[1,2|3,4,5],[1,2,3|4,5],[1,2,3,4|5]}并取最大 由此得到状态转移方程(k属于l~r-1)  特别的，因为题目中说是环形放置，我们将原序列倍增，即可枚举出环的每种情况，具体来讲就是dp数组得开两倍长...

题意  齐王和田忌各有n匹马，田忌赢得200，输得-200，平局不得钱，请你安排顺序，解出可获得的最大钱数  思路   先将齐王和田忌的马降序排序   贪心：对于齐王的第k匹马，田忌如果能赢就直接选当前第一匹马，如果不能赢就选择最后一匹马   对于平局的情况，选择第一匹和最后一匹都有可能导致错误决策   由于每一次都只有可能拿第一个和最后一个，所以剩下的一定是一个连续的区间，考虑动态规划   对于齐王的第k匹马    其中，k这个维度是没有意义的，从三维视角，固定k以后的每一层是不相交的，且总共会合成一个三角形，可以压缩到二维平面，k与l,r有关，限制方程为 ,化简得 最终状态转移方程（01滚...

题意  种物品，每种物品有 个，体积  ，价值  ，背包体积  ，求最大价值  思路  可以把每个物品直接放 次，转化为01背包，大数据会TLE 打包-二进制优化：显然，每个数n可以拆成所有不大于它的二进制次方组合+剩余部分，如此便可表示从0~n，所以对每个 进行拆分，从1开始，不断拆分，直到拆不出来，就把剩下的打包为一堆，优化后仍然是一个01背包  AC代码 #include<bits/stdc++.h> #define pii pair<int,int> #define se second #define fi first using namespace std; ...