精选优质文档-倾情为你奉上计算机算法设计与分析分治法求解多米诺骨牌 题目：现有n块“多米诺骨牌”S1，S2，Sn水平放成一排，每块骨牌Si包含左右两个部分，每个部分赋予一个非负整数值，如下图所示为包含6块骨牌的序列。骨牌可做180度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论si如何旋转，Li总是存储si左边的值，Ri总是存储右边的值，Wi用于存储si的状态：当Li=Ri时记为0，否则记为1，试采用分治法设计算法求i=1n-1RiLi+1最大值，以及当取得最大之时每个骨牌的状态。解：输入为n个多米诺骨牌S1，S2，Sn ，可将输入在中间那块骨牌的中间，即骨牌S1+n2的中间处拆分，这样原问题就被拆分为两个子问题，但是可以发现，新的子问题与原问题结构不完全一样。为解决这一问题，可对原始的输入作如下处理：此处拆分在原始输入序列左右两端各加半块骨牌，记为S0 和Sn+1 ，对应于L、R则为R0和Ln+1，并且令R0和Ln+1里面的值为0。如下图所示：则原规
