首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

插头DP小结_dp插头接线标准

插头DP一般都是棋盘模型,找路径或者环路最值或者方案数。 插头:说白了就是两个联通的格子,一个走向另一个,那么这里就有一个插头。 轮廓线:DP逐格DP,那么轮廓线可以分开DP过的格子和未DP的格子。轮廓线的长度明显是m+1。插头垂直于轮廓线。 转移: 轮廓线在换行的时候要位移,这个画画图就出来了。 然后具体问题具体讨论。比如任意多个环路,不考虑方向,那么就是eat the trees,用最小表示法,因为是任意多个环路,那么插头只有两种,一种是有插头,一种是没插头,具体联通与否我们不管。如果要考虑方向呢?那么插头就有3种,一种是没插头,一种是插头从已DP的指向未DP的,一种是未DP的指向已DP的。 具体实现,有两种思路,一种是括号序列,一种是最小表示法。 括号序列比较快,空间压缩得很好,不过转移太麻烦辣。 最小表示法转移比较好想,就是比较慢,空间比较大。 写法有三种,一种是hash表存取状态,有decode,encode,就是kuangbin那种写法;一种是传统dp写法,位运算取出状态;还有种是claris写法,预处理所有可能状态然后传统DP转移。 kuangbin那个因为位运算比较少,每次都会直接接触到解密的状态,比较直观好想,模式化很强,不过每次都有O(m)的常数用在加密解密上。时空耗费较大,要写hash表,代码较长。 传统DP转移有的是O(1),有的O(n),总体来说和上面的差不多。。因为递推转移无效状态比较多。然后代码比较短。缺点就是一堆位运算像我这种傻逼根本看不懂 claris写法太神辣。因为所有状态预处理好了所以状态数很少,因为预处理所以所有转移O(1),然后代码很短。缺点是我这种傻逼不会预处理。然后还是一堆位运算。并且遇到题目本身状态很多的时候效果不会很好。 我现在只会第一种写法。 下面扔2个例题。 HYSBZ 3125 找一条走过所有格子的环路的方案数。 有的格子只能上下经过,有的只能左右经过,有的不能经过。 这个题我写的括号序列。 插头3种,空插头,左括号,右括号。 然后分9类情况讨论即可。 因为分了9类情况所以代码长爆。

03

Java面试题全集(上)

2013年年底的时候,我看到了网上流传的一个叫做《Java面试题大全》的东西,认真的阅读了以后发现里面的很多题目是重复且没有价值的题目,还有不少的参考答案也是错误的,于是我花了半个月时间对这个所谓的《Java面试大全》进行了全面的修订并重新发布在我的CSDN博客。在修订的过程中,参照了当时JDK最新版本(Java 7)给出了题目的答案和相关代码,去掉了EJB 2.x、JSF等无用内容或过时内容,补充了数据结构和算法、大型网站技术架构、设计模式、UML、Spring MVC等内容并对很多知识点进行了深入的剖析,例如hashCode方法的设计、垃圾收集、并发编程、数据库事务等。当时我甚至希望把面试中经常出现的操作系统、数据库、软件测试等内容也补充进去,但是由于各种原因,最终只整理出了150道面试题。让我欣慰的是,这150道题还是帮助到了很多人,而且在我CSDN博客上的总访问量超过了5万次,最终还被很多网站和个人以原创的方式转载了。最近一年内,用百度搜索"Java面试"我写的这些东西基本上都排在搜索结果的前5名,这让我觉得"亚历山大",因为我写的这些东西一旦不准确就可能误导很多人。2014年的时候我又整理了30道题,希望把之前遗漏的面试题和知识点补充上去,但是仍然感觉挂一漏万,而且Java 8问世后很多新的东西又需要去总结和整理。为此,我不止一次的修改了之前的180题,修改到自己已经感觉有些疲惫或者厌烦了。2014年至今,自己带的学生又有很多走上了Java程序员、Java工程师的工作岗位,他们的面试经验也还没来得及跟大家分享,冥冥之中似乎有一股力量在刺激我要重新写一篇《Java面试题全集》,于是这篇文章就诞生了。请不要责备我把那些出现过的内容又写了一次,因为每次写东西就算是重复的内容,我也需要对编程语言和相关技术进行重新思考,不仅字斟句酌更是力求至臻完美,所以请相信我分享的一定是更新的、更好的、更有益的东西,这些内容也诉说着一个职业程序员和培训师的思想、精神和情感。

02
领券