exercise4

计算机算法设计与分析

课后习题

Last Modi?ed:2015.3.22

Exercise (4).现有n 块“多米诺骨牌”s 1,s 2,···,s n 水平放成一排，每块骨牌s i 包含左右两个部分，每个部分赋予一个非负整数值，如下图所示为包含6块骨牌的序列。骨牌可做180度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论s i 如何旋转，L [i ]总是存储s i 左边的值，R [i ]总是存储s i 右边的值，W [i ]用于存储s i 的状态：当L [i ]≤R [i ]时记为0，否则记为1，试采用分治法设计算法求∑n ?1i =1R [i ]·L [i +1]的最大值，以及当取得最大值时每个骨牌的状态。5

8s 142s 296s 377s 439s 51110s 6

deadline:2015.04.11

1