PKU acm 1651 multiplication puzzle

10 1 50 20 5

player might take a card with 1, then 20 and 50, scoring

10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be

1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

不能取第一个和最后一个数字，我们的目的是将其余数字全部取出，并且使得按照规则计算的分数最小。

计分规则是，每取一个a, 计算 score.a = a.left * a * a.right然后将a取出，最后的总分是每次取出计算得出的分值总和。

 

动态规划，思路和矩阵连乘几乎一致。

考虑

10 1 50 20 5

对于最优解，取最后一个数字，假如说最后一个数字取的是50，那么其实

10 1 50

50 20 5

是两个子问题，他们也应该是最优的，而最后结果是

10 * 50 * 5 + best(10,1,50) + best(50,20,5)

 

best resutl  of li = best[0, len – 1]

 

best[i, j] =  min { li[i] * li[k] * li[j] + best[i, k] + best[k, j]} for k in range [i+1, j)

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int SolveDp(int a[], int num)
 5 {
 6     int result[num][num];
 7     for (int i = 0; i < num; i++)
 8         for (int j = 0; j < num; j++)
 9             result[i][j] = 0;
 
     //init delta = 2 a[0] a[1] a[2]
     for (int i = 0; i < num - 2; i++)
         result[i][i + 2] = a[i] * a[i + 1] * a[i + 2];
 
     for (int delta = 3; delta < num; delta++)
         for (int i = 0; i < num - delta; i++) {
             int minScore;
             for (int j = i + 1; j < i + delta; j++) {
                 int curScore = result[i][j] + result[j][i + delta] + 
                                a[i] * a[j] * a[i +delta];
                 if(j == i + 1)
                     minScore = curScore;
                 else if (curScore < minScore)
                     minScore = curScore;
             }
             result[i][i + delta] = minScore;
         }
     return result[0][num - 1];
 }
 
 int main(int argc, char *argv[])
 {
     //while(1) {
         int num;
         cin >> num;
         int a[num];
         for (int i = 0; i < num; i++)
             cin >> a[i];
         cout << SolveDp(a, num) << endl;
     //}
     return 0;
 }

下面给出python写的，递归回溯（穷举），以及动态规划解法

 1 #递归回溯穷举
 2 def findMinScore(li):
 3     minScore = -1  #init,if not touched it will be < 0
 4     def findMinScoreRec(score = 0):
 5         nonlocal minScore
 6         length = len(li)
 7         for i in range(1, length - 1):
 8             val = li[i]
 9             newScore =  score + li[i - 1] * val * li[i + 1]
             if not minScore < 0 and newScore > minScore:
                 return
             if len(li) == 3:
                 if minScore <0 or newScore < minScore:
                     minScore = newScore
                 return
             li.pop(i)
             findMinScoreRec(newScore)
             li.insert(i, val)  #do not need to get back
     print("min score is ", minScore);        
     findMinScoreRec();
     return minScore
  1 #dp method

 2 def findMinScore(li):
 3     length = len(li)
 4     #below is wrong!!! when result[0][2] = 99 than result[i][2] = 99 why??
 5     #result = [[0] * length] * length  #result[length][length] 0 is must for elements of distance 2
 6     
 7     result = [[0   for   a   in   range(length)]   for   b   in   range(length)]
 8     
 9     for i in range(length - 2):
         result[i][i + 2] = li[i] * li[i + 1] * li[i + 2]
     
     for delta in range(3, length):
         for i in range(length - delta):
             for j in range(i + 1, i + delta):
                 curScore = result[i][j] + result[j][i + delta] \
                     + li[i] * li[j] * li[i + delta]
                 if (j == i + 1 or curScore < minScore):
                     minScore = curScore
             result[i][i + delta] = minScore
     
     return result[0][length - 1]