有向无环图(DAG,Directed Acyclic Graph)上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。 题目描述:       有n个矩形,每个矩形可以用两个整数a,b描述,表示它的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d,或者b<c,a<d(相当于把矩形X旋转90°)。例如(1,5)可以嵌套在(6,…

2014年5月17日 0条评论 2点热度 阅读全文

    本文主要讲述KMP已经KMP的一种改进方法。若发现不正确的地方,欢迎交流指出,谢谢! KMP算法的基本思想: KMP的算法流程: 每当一趟匹配过程中出现字符比较不等时,不需回溯 i 指针,而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后,继续进行比较。 设S为目标串,T为模式串,设 i 指针和 j 指针分别指示目标串和模式串中正待比较的字符。 开始时,令i=0,j=0。如果Si==Tj,则使i和j的值分别增加l;反之,i不变,j的值退回到j=next[j]的位…

2012年11月8日 0条评论 2点热度 阅读全文