<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[The_sam的博客]]></title><description><![CDATA[在路上的码农]]></description><link>https://blog.csdn.net/The_sam</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; The_sam]]></copyright><item><title><![CDATA[ACM 粗心永远AC不了系列——Demo Day|三维DP问题，机器人寻路，hiho一下第150周]]></title><link>https://blog.csdn.net/The_sam/article/details/72132966</link><guid>https://blog.csdn.net/The_sam/article/details/72132966</guid><author>The_sam</author><pubDate>Mon, 15 May 2017 13:13:36 +0800</pubDate><description><![CDATA[题目来源：https://hihocoder.com/contest/hiho150/problem/1
时间限制:10000ms



单点时限:1000ms
内存限制:256MB





描述
You work as an intern at a robotics startup. Today is your company's demo day. During t]]></description><category></category></item><item><title><![CDATA[算法导论——26.2 FordFulkerson方法，Edmonds-Karp算法java实现]]></title><link>https://blog.csdn.net/The_sam/article/details/71456465</link><guid>https://blog.csdn.net/The_sam/article/details/71456465</guid><author>The_sam</author><pubDate>Tue, 09 May 2017 14:23:35 +0800</pubDate><description><![CDATA[介绍
由Ford 和Fulkerson于1956年提出最大流问题的标号算法，故又称 Ford–Fulkerson标号法。其基本思想就是，从一个可行流开始，寻找从s到t的增广链，然而沿增广链增加流量，反复这样，直到找不出增广链位置。
更多内容参见博文http://blog.csdn.net/smartxxyx/article/details/9293665
这里值得注意的是，这个方法各种实现算]]></description><category></category></item><item><title><![CDATA[算法导论——24.3 Dijkstra最短路径算法java实现]]></title><link>https://blog.csdn.net/The_sam/article/details/71438170</link><guid>https://blog.csdn.net/The_sam/article/details/71438170</guid><author>The_sam</author><pubDate>Tue, 09 May 2017 00:44:33 +0800</pubDate><description><![CDATA[Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

　　其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不]]></description><category></category></item><item><title><![CDATA[算法导论——24.2 DAG最短路径算法java实现]]></title><link>https://blog.csdn.net/The_sam/article/details/71437340</link><guid>https://blog.csdn.net/The_sam/article/details/71437340</guid><author>The_sam</author><pubDate>Mon, 08 May 2017 23:43:45 +0800</pubDate><description><![CDATA[Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题，但是对于DAG，可以有更加简化的算法去计算，使得时间复杂度更低。
针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单算法。通过理论分析,表明该算法具有理想的运算效率,其中,解决单源点问题的运算时间与E成正比,解决所有点对问题的运算时间与VE成正比。拓扑排序策略对于此类最短路径问题的研究,较传统的方法运算简单、求解直观。]]></description><category></category></item><item><title><![CDATA[算法导论——24.1 BellmanFord算法java实现]]></title><link>https://blog.csdn.net/The_sam/article/details/71436297</link><guid>https://blog.csdn.net/The_sam/article/details/71436297</guid><author>The_sam</author><pubDate>Mon, 08 May 2017 21:43:11 +0800</pubDate><description><![CDATA[Bellman - ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。其原理为持续地进行松弛（原文是这么写的，为什么要叫松弛，争议很大），在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。Bellman - ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间去做没有必要的松弛，而SPFA算法用队列进行]]></description><category></category></item><item><title><![CDATA[ACM 粗心永远AC不了系列——小Hi的烦恼|“五维数点”问题]]></title><link>https://blog.csdn.net/The_sam/article/details/70982091</link><guid>https://blog.csdn.net/The_sam/article/details/70982091</guid><author>The_sam</author><pubDate>Sat, 29 Apr 2017 18:02:55 +0800</pubDate><description><![CDATA[问题来源：hiho一下第147周 小Hi的烦恼



题目1 : 小Hi的烦恼




时间限制:5000ms
单点时限:1000ms
内存限制:1024MB






描述
小Hi从小的一大兴趣爱好就是学习，但是他发现尽管他认真学习，依旧有学神考的比他好。
小Hi在高中期间参加了市里的期末考试，一共五门：语文、数学、英语、物理、化学。
成绩出来之后，小]]></description><category></category></item><item><title><![CDATA[ACM 粗心永远AC不了系列——HDU 1754 I Hate It|线段树区间求最值]]></title><link>https://blog.csdn.net/The_sam/article/details/70948255</link><guid>https://blog.csdn.net/The_sam/article/details/70948255</guid><author>The_sam</author><pubDate>Sat, 29 Apr 2017 13:30:36 +0800</pubDate><description><![CDATA[线段树应用水题之一

一：线段树基本概念

1：概述
线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!
性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍]]></description><category></category></item><item><title><![CDATA[动态规划==》京东机2017实习生考题，通过概率]]></title><link>https://blog.csdn.net/The_sam/article/details/69661387</link><guid>https://blog.csdn.net/The_sam/article/details/69661387</guid><author>The_sam</author><pubDate>Fri, 07 Apr 2017 21:52:26 +0800</pubDate><description><![CDATA[题目描述
									小明同学要参加一场考试，考试一共有n道题目，小明必须做对至少60%的题目才能通过考试。考试结束后，小明估算出每题做对的概率，p1,p2,...,pn。你能帮他算出他通过考试的概率吗？输入输入第一行一个数n（1样例输入450
 50 50 50输出小明通过考试的概率，最后结果四舍五入，保留小数点后五位。样例输出0.31250时间限制C/C++语言：1000MS其它语言：]]></description><category></category></item><item><title><![CDATA[动态规划入门==》转换为DAG问题——钢条切割]]></title><link>https://blog.csdn.net/The_sam/article/details/69400589</link><guid>https://blog.csdn.net/The_sam/article/details/69400589</guid><author>The_sam</author><pubDate>Thu, 06 Apr 2017 18:38:41 +0800</pubDate><description><![CDATA[问题描述：

       一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下：

1.数据结构表示DAG，我们可以把它想象成DAG，每个长度想象成一个点，i>j  则i可以指向j，代价为上图（i-j）对应数值，结果就是求最长路径。

2.问题小化，即求出前]]></description><category></category></item><item><title><![CDATA[动态规划入门==》转换为DAG问题——最短路径|矩阵嵌套|硬币问题]]></title><link>https://blog.csdn.net/The_sam/article/details/68492011</link><guid>https://blog.csdn.net/The_sam/article/details/68492011</guid><author>The_sam</author><pubDate>Thu, 30 Mar 2017 19:31:44 +0800</pubDate><description><![CDATA[动态规划刚刚开始学习，到现在做过几道题，借鉴了各位大神的书籍文章后，对其有了新的看法。
现在我总结目前我遇到题目动态规划思想的共性——很多动态规划都可以转化为带权DAG问题，以下是几道题题，我从中总结了他们的DAG特性
一、DAG最短路径
在我们聊DAG时先来介绍一个最直接的DAG问题

问题描述：
给一个带权有向无环图G=（V，E），找出这个图里S==>E的最短路径。

这个问题]]></description><category></category></item><item><title><![CDATA[算法导论——16.1-5动态规划解决活动选择带值问题]]></title><link>https://blog.csdn.net/The_sam/article/details/67645762</link><guid>https://blog.csdn.net/The_sam/article/details/67645762</guid><author>The_sam</author><pubDate>Tue, 28 Mar 2017 20:54:01 +0800</pubDate><description><![CDATA[原活动问题是用贪心算法解得，实质是就是不重合区间择多问题。
新的问题变形后，每个区间的都带上的值，求如何选择才能得到不重合区间且值最大。
想了想只能用dp来解决，下面附我的解题思路+代码
       1.用act[max][3]记录所有活动的状态（开始时间|结束时间|价值）

         act[n-1][0]表示第n个活动的开始时间，act[n-1][1]]表示第n个活动的结束]]></description><category></category></item><item><title><![CDATA[盛大游戏面试题目小结]]></title><link>https://blog.csdn.net/The_sam/article/details/66991217</link><guid>https://blog.csdn.net/The_sam/article/details/66991217</guid><author>The_sam</author><pubDate>Mon, 27 Mar 2017 23:17:40 +0800</pubDate><description><![CDATA[额，第一次面试，自己知识库还没有补充足，果然面完整个人都感觉不好了，这里会议起面试的问题，并贴出总结的答案，如果有哪里理解的不对，欢迎指正。
1.线程安全的队列
java提供线程安全的队列，主要分两种：阻塞队列（接口 BlockingQueue）和非阻塞队列（类ConcurrentLinkedQueue）
     阻塞队列就是提供阻塞操作，当操作失败时阻塞线程（ReentrantLock]]></description><category></category></item><item><title><![CDATA[三次握手与四次挥手示意图]]></title><link>https://blog.csdn.net/The_sam/article/details/65445286</link><guid>https://blog.csdn.net/The_sam/article/details/65445286</guid><author>The_sam</author><pubDate>Thu, 23 Mar 2017 16:34:58 +0800</pubDate><description><![CDATA[关于三次握手和四次挥手，大家可参考一下这篇博文，介绍的很详细，这里我主要以简单易懂的图生动概述一下]]></description><category></category></item><item><title><![CDATA[ACM 粗心永远AC不了系列——UVA 512 - Spreadsheet Tracking  追踪电子表格中的单元格 |变换思想的另一种思路]]></title><link>https://blog.csdn.net/The_sam/article/details/61920961</link><guid>https://blog.csdn.net/The_sam/article/details/61920961</guid><author>The_sam</author><pubDate>Mon, 13 Mar 2017 16:41:45 +0800</pubDate><description><![CDATA[此题在算法竞赛入门经典第二版中85页有详解，我先自己想了一下思路，然后看书上的思路，发现书上第二中方法的思路非常的巧妙，在不看代码的情况下自己实现了，特此标记。
题目详细在最下方，这里先总结我的一点小小的心得。
此题模拟Excel的变换，最首先想到的思路是用一个二维数组来模拟该操作，只不过这样子会使整个算法效率很地底下，但是较为容易想到。
另一种思路，变换类型的题，但凡他是要求结果不论过程的]]></description><category></category></item><item><title><![CDATA[ACM 粗心永远AC不了系列——UVa 213 Message Decoding(World Finals1991，字符串) |二维数组的妙用]]></title><link>https://blog.csdn.net/The_sam/article/details/61916527</link><guid>https://blog.csdn.net/The_sam/article/details/61916527</guid><author>The_sam</author><pubDate>Mon, 13 Mar 2017 13:55:21 +0800</pubDate><description><![CDATA[每天进步一点点，早日脱离水坑]]></description><category></category></item><item><title><![CDATA[《μCOS-III源码分析笔记》学习笔记|2|第三章时间管理]]></title><link>https://blog.csdn.net/The_sam/article/details/61421125</link><guid>https://blog.csdn.net/The_sam/article/details/61421125</guid><author>The_sam</author><pubDate>Sat, 11 Mar 2017 21:18:41 +0800</pubDate><description><![CDATA[第3章时间管理
3.1时间管理API

3.2API原理
OSTimeDly()和OSTimeDlyHMSM()的原理都是根据任务和其需要延时的节拍，调用OS_TickListInset()来讲该任务插入到时钟节拍轮（OSCfg_TickWheel[] 详见上章）中，并把该任务从就绪队列中脱离。

之后每个时钟节拍都会判断任务延时是会否结束，结束了就把任务脱离时钟节拍轮，进行下一步操作]]></description><category></category></item><item><title><![CDATA[《μCOS-III源码分析笔记》学习笔记|1|第二章时钟节拍]]></title><link>https://blog.csdn.net/The_sam/article/details/61419728</link><guid>https://blog.csdn.net/The_sam/article/details/61419728</guid><author>The_sam</author><pubDate>Sat, 11 Mar 2017 16:11:03 +0800</pubDate><description><![CDATA[《μCOS-III源码分析笔记》学习笔记|1|第二章时钟节拍
学校开源代码分析课程
有是一门操作系统]]></description><category></category></item><item><title><![CDATA[ACM 粗心永远AC不了系列——HDU 1097 A hard puzzle]]></title><link>https://blog.csdn.net/The_sam/article/details/59559193</link><guid>https://blog.csdn.net/The_sam/article/details/59559193</guid><author>The_sam</author><pubDate>Thu, 02 Mar 2017 17:09:24 +0800</pubDate><description><![CDATA[为什么ACM过不了，就是因为太年轻了，ACM需要考虑的比较细心，只有慢慢耐心才能积累经验养成好的编程习惯，加油奋斗。]]></description><category></category></item></channel></rss>