习题16.1-4 区间图着色问题。边最多的顶点G,其边数n即需要的颜色数,也即教室数。有n种颜色,顶点标为第i种颜色,则此活动可放在第i个教室举行。从一顶点开始广度优先遍历,将相连接的点标为不同颜色,标颜色同时检查与此相连的所有点颜色不同。然后检查全部顶点,有未标色的顶点,按照上法重新开始标色。 习题16.1-5 如果每个活动有值vk,要求vk总和的最大值,那么这个题就需要用动态规划求解了。时间为i,若有一个完成的活动,此活动编号为j,则D[i]=max( D[i- tj] + v[j] , D[i-1] ),表格…

2015年2月9日 0条评论 4点热度 阅读全文

习题16.1-4 区间图着色问题。边最多的顶点G,其边数n即需要的颜色数,也即教室数。有n种颜色,顶点标为第i种颜色,则此活动可放在第i个教室举行。从一顶点开始广度优先遍历,将相连接的点标为不同颜色,标颜色同时检查与此相连的所有点颜色不同。然后检查全部顶点,有未标色的顶点,按照上法重新开始标色。 习题16.1-5 如果每个活动有值vk,要求vk总和的最大值,那么这个题就需要用动态规划求解了。时间为i,若有一个完成的活动,此活动编号为j,则D[i]=max( D[i- tj] + v[j] , D[i-1] ),表格…

2015年2月9日 0条评论 3点热度 阅读全文

动态顺序统计。一种是红黑树结点储存附加子树的元素数size。一种是储存中序遍历的秩r。插入、删除时对附加属性的维护。相类似的扩展的红黑树附加属性f若仅依赖于x、x.left、x.right,还可能包括x.left.f与x.right.f,则插入删除时维护所有结点的属性f,不影响O(lg(n))渐近性能。 区间树。区间属性x.int,关键字x.int.low,构成红黑树,节点附加属性x.max=max(x.left.max, x.int.high, x.right.max)。 interval_insert(T, x…

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