多米诺骨牌问题
多米诺骨牌
现有n块”多米诺骨牌”s1,s2,s3,...sn水平放成一排,每次骨牌si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列.骨牌可做180度旋转,使得原来在左边的值变到右边,而原来右边的值移到左边,假设不论si如何旋转,L[i]总是存储si左边的值, R[i]总是存储si右边的值, W[i]用于存储si的状态:当L[i]<=R[i]时记为0,否则记为1,试采用分治法设计算法求:R[1]*L[2]+R[2]*L[3]+R[3]*L[4]+R[4]*L[5]+...++R[n-1]*L[n]的最大值,以及当取得最大值时每个骨牌的状态.
5|8 4|2 9|6 7|7 3|9 11|10
s1 s2 s3 s4 s5 s6
请各位仁兄讲讲解题的思路，小弟不甚感激！
[解决办法]
看条件限制。容易设计O(n^4)的分治算法。
[解决办法]
应该是n^2
