- 博客(17)
- 收藏
- 关注
RSS订阅原创 动态规划经典最优子结构总结
（1）0-1背包：如果有一个背包，总载重量为Wt，有n个物品，每个物品重Wi，每个物品价值Ci，那么如何装才能让这个包里面东西的价值最高？dp[i][j]为前i个物品当中选择装进一个载重量为j的包里最大价值，则：初始化：dp【0】【x】=0；for i=0-》n；j=0-》Wtdp[i][j]的值为：dp[i-1][j]（第i个物品不装进包里）,dp[i-1][j-Wi]+Ci（第
2016-05-22 23:25:05
7713
原创 2016年蓝桥个人赛赛前总复习 个人经验总结
20号就是蓝桥杯的省赛了，准备了半年，现在进入了最后的准备阶段，把几大经典算法和一些C++ 上必备的技巧做一个总结。第一，dijkstra。为什么从dijkstra说起，因为这是最经典，最基础，使用率最广的图算法之一。void dijkstra(){ int path[v+1]; int shortest[v+1] int shortestPoint; int shortest
2016-03-16 22:13:39
1060
1
原创 poj1837 动态规划和01背包问题延伸的经典题目，很值得一做
首先说一下基本思路，是按照小优博客上来的思路，即平衡度来做的，其博主在博客上写得已经非常全面了，这里转载一下：来源：http://blog.csdn.net/lyy289065406/article/details/6648094/每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状态获得。 首先定义一个平衡度j的概念当平衡度j=0时，说明天枰达到平衡，j>0，
2016-03-13 21:50:58
829
原创 poj1459 网络最大流问题 ek算法
1459是一道经典的最大流问题，很适合练手，最大流问题有很多算法，经典的像ek、km，在ACM比赛中，一般由于时间紧迫，比较适合用ek，因为直观，写起来不是很费力。下面来回顾一下ek算法的经典流程，ek算法有两个函数组成：1.ek主函数；2.dfs函数。ek主函数的输入参数为起始编号，终止编号：void ek(int start,int end){int max=0; int
2016-03-10 16:45:42
596
原创 POJ3020 无向图的最小路径覆盖 无向图边覆盖 匈牙利算法巩固训练
很经典的一道题目，做了好几遍，每次都很好地回顾了匈牙利算法。解决无向图边覆盖问题的步骤如下：1.拆点；2.求拆点后图的最小点覆盖，即最大匹配数；3.使用公式：最小路径覆盖=拆点前点的数量-最大匹配数/2。回顾一下匈牙利算法的解题过程：for(int i=1;i<=xNum;i++){ for(int j=1;j<=yNum;j++){ ifVisited[j]=fal
2016-03-09 14:50:00
1261
原创 POJ3041 最小点覆盖 最大匹配数 回顾匈牙利算法
DescriptionBessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 Fortunately, Bessie has a powerful weapon that can vaporize all the astero
2016-03-08 20:35:33
498
原创 基本算法prim学习总结性文章
Prim算法是最简单也是最直观的求最小生成树的算法，与kruskal相比，具有代码量小的特点，避免了kruskal寻找祖先等复杂数据结构，在ACM比赛中，因为时间紧张，采用prim的情况无疑比kruskal更多。prim需要的数据结构有：int miniestPoint; 这轮路径最短的点int miniestDist; 这轮最短的路径int currentDist[];
2016-03-08 19:25:22
593
原创 基本算法floyd的poj水题推荐
首先回忆一下floyd的数据结构：floyd是最直观的最短路径算法，只需要图数组即可。图数组chart[][];回顾一下floyd的基本过程：for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ for(int k=1;k<=v;k++){ if(chart[j][k]>chart[j][i]+chart[i][k]){ c
2016-03-07 21:55:27
1123
原创 基本算法dijkstra的POJ水题推荐
首先转载一个别人归纳的题目集合：1.poj1062 昂贵的聘礼（中等） 此题是个经典题目；用Dijkstra即可；但是其中的等级处理需要一定的技巧； 要理解好那个等级制度；这个处理好，基本就是裸体Dijkstra；2 poj1125 Stockbroker Grapevine（基本） 这个是简单Floyd，需要求出的是每对顶点之间的最短路径； 然后找到那个
2016-03-07 21:49:41
1899
1
转载 ACM推荐题目汇总
目前比较知名的两个ACM推荐题目集合：一、POJ推荐50题1、标记“难”和“稍难”的题目可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。2、标记为A and B的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。3、列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。4、这里不少题目在BUPT ACM FTP上面都有
2016-03-07 21:40:00
3411
原创 2016华为软件精英挑战赛初赛题目，个人分析与代码，尚未测试代码，因为没有judge系统啊！
看到题目，首先想到这是一个哈密顿回路的题，但是不是简单的哈密顿回路，因为题目中要求走过的点不是所有点，而是所有点V的一个子集V'，所以在求出一个到达终点的路径之后，做一个判断，看path是否经历过所有的V'就行了，而不需要像求哈密顿回路一样，去设置一个数字cur，当cur==V个数时才判断是否能到达终点。哈密顿回路是np问题，目前比较直观的解法是采用dfs。因此这道题目对dfs做了考察，另
2016-03-04 19:28:23
10298
14
原创 bellman-ford 学习总结性文档
bellman-ford和dijkstra一样，是求最短路径的算法，和dijkstra一样，都是输入一个点，输出这个点到其他所有点的最短路径，这个算法的通用性更广，因为它可以很好地支持包含负权的图，而dijkstra不行，算法如下使用：输入：输入一个起点；输出：输出这个起点到所有点的最短路径（如果有）；输出错误信息（如果存在负权回路）。算法过程如下：初始化各边最短路径长度：
2016-03-03 19:20:57
533
原创 POJ1011 一种dfs实现
//已经删掉了剪枝，如果要AC还要继续剪枝，思路大家可以自己思考一下//本题主要使用的思想是DFS的第三种类型，还原现场，DFS三种类型详情可参阅本人博客POJ1015那篇#include#include#includeusing namespace std;int n;int maxx;int minx;int d[65];bool v[65];int cmp(con
2015-12-27 15:04:33
400
原创 POJ1015 Jury Compromise dfs的实现
做ACM练习题目已经两个年头了，最开始脑子很混乱，后来慢慢有了感觉，AC率也大幅度提高，接下来就一些经典问题做一下回顾，这些问题涵盖了算法的多个方面，相对来说有一些较为全面的总结，也是我这些年劳动成果的一些体现，今天带来的是另一道经典题目1015的dfs实现。首先需要说明的是，这道题系统要求是用动态规划来做，并且只有动态规划能够在规定时间内跑完。这里我要说的是dfs的实现，这种实现是不能AC的
2015-12-27 13:31:37
506
原创 C++快速实现String到int int到String 转换 JAVA
JAVA中iString转int可以借助String.ValueOf(int i)来实现，转换后的结果是
2015-12-26 15:03:56
1298
原创 POJ 2479 动态规划 最大子序列问题（两段） Maximum sum
做ACM练习题目已经两个年头了，最开始脑子很混乱，后来慢慢有了感觉，AC率也大幅度提高，接下来就一些经典问题做一下回顾，这些问题涵盖了算法的多个方面，相对来说有一些较为全面的总结，也是我这些年劳动成果的一些体现，这是第一篇，带来的是经典动态规划问题——最大子序列。题目如下DescriptionGiven a set of n integers: A={a1, a2,...,
2015-12-25 20:28:42
755
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人