算法作业6袁胜_2016M8009073008

Python

基本思路

采用自底向上的动态规划法。

• 每相邻的两个骨牌，组合方式有00, 01, 10, 11四种。
• 首先分别计算 $s_1, s_2$ 的00，10组合（即以0结尾的组合）的 $R[i]L[i+1]$ ，将其中较大者赋值给 Ends0；分别计算01，11两个组合（即以1结尾的组合）的 $R[i]L[i+1]$ ，将其中的较大者赋值给 Ends1。并分别记录组合序列，其余的组合忽略掉。
• 对于$s_2, s_3$ 两张骨牌，将00, 01组合（即以0开头的组合）计算出的 $R[i]L[i+1]$ 分别与 Ends0 相加；将10, 11组合（即以1开头的组合）的 $R[i]L[i+1]$ 分别与Ends1相加。得到的4个结果中，将序列以0结尾的2个结果中较大的记录到 Ends0；将序列以1结尾的2个结果中较大的记录到 Ends1。其余2个结果忽略掉，并记录 Ends0 和 Ends1 的组合序列。
• ...
• 对于$s_k$与$s_{k+1}$两张骨牌，与步骤2相同，
  $Sum00=Ends0+f00$
  $Sum01=Ends0+f01$
  $Sum10=Ends1+f10$
  $Sum11=Ends1+f11$
  $Ends0=Max(Sum00, Sum10)$
  $Ends1=Max(Sum01, Sum11)$
• 这样每次累加后，都将以0结尾的组合序列中的最大者记录到Ends0，将以1结尾的组合序列中的最大者记录到 Ends1，将其余的组合舍去，并记录 Ends0 和 Ends1 的组合序列。
• 最终，计算了 $s_{n-1}$ 和 $s_n$ 之后， Ends0 和 Ends1中较大的值即为所求的最大值，相应的组合序列即为最终所求的组合序列。

伪码

Algorithm Domino(s[]):
    n <- Length(s);
    Ends0 <- 0;
    Ends1 <- 0;
    Stat0 <- '0'; #Ends0的组合序列字符串
    Stat1 <- '1'; #Ends1的组合序列字符串
    for (i in 0..n-2):
        f00 <- s[i]与s[i+1]在组合00的情况下的R[i]*L[i+1];
        f01 <- s[i]与s[i+1]在组合01的情况下的R[i]*L[i+1];
        f10 <- s[i]与s[i+1]在组合10的情况下的R[i]*L[i+1];
        f11 <- s[i]与s[i+1]在组合11的情况下的R[i]*L[i+1];
        Sum00 <- Ends0 + f00; 
        Stat00 <- Stat0 连接 '0';
        Sum01 <- Ends0 + f01; 
        Stat01 <- Stat0 连接 '1';
        Sum10 <- Ends1 + f10; 
        Stat10 <- Stat1 连接 '0';
        Sum11 <- Ends1 + f11; 
        Stat11 <- Stat1 连接 '1';
        Ends0 <- Max(Sum00, Sum10); 记录 Stat0;
        Ends1 <- Max(Sum01, Sum11); 记录 Stat1;
    end
    return Max(Ends0, Ends1);

时间复杂度分析

对于所有 $s_i$ $(i = [1..n])$ 骨牌，每次循环需要计算：
- $s_i$与$s_{i+1}$的00, 01, 10, 11四种组合的 $R[i]L[i+1]$ 的值。
- 将00, 01两个组合计算的结果与 Ends0 相加得(Sum00, Sum01)；
- 将10, 11两个组合计算的结果与 Ends1 相加得(Sum10, Sum11)；
- 将 Max(Sum00, Sum10)记录到 Ends0；
- 将 Max(Sum01, Sum11)记录到 Ends1；

以上计算的时间复杂度为常数级O(C)。
循环一共执行 n-1 次。
$\therefore T(n) = C(n-1)$，即时间复杂度为$O(n)$，复合题目要求。

计算过程

以题目中的骨牌序列为例。
$s1:\fbox {5 | 8}$ $s2:\fbox {4 | 2}$ $s3:\fbox {9 | 6}$ $s4:\fbox {7 | 7}$ $s5:\fbox {3 | 3}$ $s6:\fbox {11|10}$

step1

计算 s1,s2 两张骨牌在00, 01, 10, 11四种组合下的 $R[i]L[i+1]$
$f00 - \fbox {5 | 8} ,\fbox {2 | 4} - R[1]L[2]=16$
$f01 - \fbox {5 | 8} ,\fbox {4 | 2} - R[1]L[2]=32$
$f10 - \fbox {8 | 5} ,\fbox {2 | 4} - R[1]L[2]=10$
$f11 - \fbox {8 | 5} ,\fbox {4 | 2} - R[1]L[2]=20$

在以0结尾的组合中，f00较大，遂舍弃f10，Ends0=f00=16
在以1结尾的组合中，f01较大，遂舍弃f11，Ends1=f01=32

Ends0序列为00
Ends1序列为01

step2

计算 s2,s3 两张骨牌在00, 01, 10, 11四种组合下的 $R[i]L[i+1]$
$f00 - \fbox {2 | 4} ,\fbox {6 | 9} - R[2]L[3]=24$
$f01 - \fbox {2 | 4} ,\fbox {9 | 6} - R[2]L[3]=36$
$f10 - \fbox {4 | 2} ,\fbox {6 | 9} - R[2]L[3]=12$
$f11 - \fbox {4 | 2} ,\fbox {9 | 6} - R[2]L[3]=18$

$Sum00 = Ends0 + f00 = 16 + 24 = 40$
$Sum01 = Ends0 + f01 = 16 + 36 = 52$
$Sum10 = Ends1 + f10 = 32 + 12 = 44$
$Sum11 = Ends1 + f11 = 32 + 18 = 50$

$Ends0=Max(Sum00, Sum10)=Max(40, 44)=44$
$Ends1=Max(Sum01, Sum11)=Max(52, 50)=52$

Ends0序列为010
Ends1序列为001

step3

计算 s3,s4 两张骨牌在00, 01, 10, 11四种组合下的 $R[i]L[i+1]$
$f00 - \fbox {6 | 9} ,\fbox {7 | 7} - R[3]L[4]=63$
$f01 - \fbox {6 | 9} ,\fbox {7 | 7} - R[3]L[4]=63$
$f10 - \fbox {9 | 6} ,\fbox {7 | 7} - R[3]L[4]=42$
$f11 - \fbox {9 | 6} ,\fbox {7 | 7} - R[3]L[4]=42$

$Sum00 = Ends0 + f00 = 44 + 63 = 107$
$Sum01 = Ends0 + f01 = 44 + 63 = 107$
$Sum10 = Ends1 + f10 = 52 + 42 = 94$
$Sum11 = Ends1 + f11 = 52 + 42 = 94$

$Ends0=Max(Sum00, Sum10)=Max(107, 94)=107$
$Ends1=Max(Sum01, Sum11)=Max(107, 94)=107$

Ends0序列为0100
Ends1序列为0101

step4

计算 s4,s5 两张骨牌在00, 01, 10, 11四种组合下的 $R[i]L[i+1]$
$f00 - \fbox {7 | 7} ,\fbox {3 | 9} - R[4]L[5]=21$
$f01 - \fbox {7 | 7} ,\fbox {9 | 3} - R[4]L[5]=63$
$f10 - \fbox {7 | 7} ,\fbox {3 | 9} - R[4]L[5]=21$
$f11 - \fbox {7 | 7} ,\fbox {9 | 3} - R[4]L[5]=63$

$Sum00 = Ends0 + f00 = 107 + 21 = 128$
$Sum01 = Ends0 + f01 = 107 + 63 = 170$
$Sum10 = Ends1 + f10 = 107 + 21 = 128$
$Sum11 = Ends1 + f11 = 107 + 63 = 170$

$Ends0=Max(Sum00, Sum10)=Max(128, 128)=128$
$Ends1=Max(Sum01, Sum11)=Max(170, 170)=170$

Ends0序列为01000 (选第1个)
Ends1序列为01011 (选第1个)

step5

计算 s5,s6 两张骨牌在00, 01, 10, 11四种组合下的 $R[i]L[i+1]$
$f00 - \fbox {3 | 9} ,\fbox {10|11} - R[5]L[6]=90$
$f01 - \fbox {3 | 9} ,\fbox {11|10} - R[5]L[6]=99$
$f10 - \fbox {9 | 3} ,\fbox {10|11} - R[5]L[6]=30$
$f11 - \fbox {9 | 3} ,\fbox {11|10} - R[5]L[6]=33$

$Sum00 = Ends0 + f00 = 128 + 90 = 218$
$Sum01 = Ends0 + f01 = 128 + 99 = 227$
$Sum10 = Ends1 + f10 = 170 + 30 = 200$
$Sum11 = Ends1 + f11 = 170 + 33 = 203$

$Ends0=Max(Sum00, Sum10)=Max(218, 200)=218$
$Ends1=Max(Sum01, Sum11)=Max(227, 203)=227$

$Ends1为最终所求的最大值227。序列为010001。$