本文共 2008 字，大约阅读时间需要 6 分钟。

题目链接：

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points. For example, if cards in the row contain numbers 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.

Input

The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer - the minimal score.

Sample Input

610 1 50 50 20 5

Sample Output

3650

 

题目翻译：

‎乘法谜题使用一行牌进行,每张卡片包含一个正整数。在移动过程中,玩家从行中取出一张牌,并将积分数与所采集卡上的数字和左侧和右侧牌上的数字的分数相等。不允许拿出行中的第一张和最后一张牌。最后移动后,该行中仅剩下两张牌。‎

‎目标是以尽可能减少得分总数的顺序来获取‎ ‎牌。‎ ‎例如,如果行中的牌包含数字 10 1 50 20 5,则玩家可能会拿一张卡片,其中 1,然后是 20 和 50,‎ ‎得分‎

‎10*1*50 * 50*20*5 * 10*50*5 * 500*500*500*2500 * 8000‎

‎如果他以相反的顺序,即50,然后20,然后1,分数将是‎

‎1*50*20 * 1*20*5 * 10*1*5 * 1000*100*50 * 1150。‎

‎输入‎

‎输入的第一行包含卡数 N (3 <= N <= 100)。第二行包含 1 到 100 范围内的 N 个整数,由空格分隔。‎

‎输出‎

‎输出必须包含单个整数 - 最小分数。‎

 

经典的区间dp题，在刘汝佳的紫书（P277）里面也有关于这部分的解析，就不多讲了，具体分析请参考书中的内容。

这个题有两种方法，递推和记忆化搜索，注意递推是要注意 i 和 j 在for循环中的顺序，是按照j-i递增的顺序递推的。

下面给出记忆化搜索的代码和解析

状态：dp[i][j]表示从i区间到j区间的最小分数

转移方程：dp[i][j]=min{dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]}

边界条件：dp[i][i+1]=0

#include 
   
    #include
    
      #include
     
      using namespace std;const int INF=0x3f3f3f3f;int n,a[105],dp[105][105];int solve(int i,int j){	if(dp[i][j]!=INF) return dp[i][j];	if(j==i+1) return 0;	for(int k=i+1;k
     
    
   

 

转载地址：http://xifmz.baihongyu.com/