6959: POJ1651 - Multiplication Puzzle
[Creator : ]
Description
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$.
给你一个序列 ，你要在其中选择 $n-2$ 个数，每个数取出来的时候，结果 要加上 它乘以它左边的再乘以它右边的，也就是 a[i]*a[i-1]*a[i+1]，当然取出后，左右的数据就变化了，题目要求最左端和最右端的两个数不能取，要求选择最合适的顺序去取出这 $n-2$ 个数。
During the move pla
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$, pla
$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$.
给你一个序列 ，你要在其中选择 $n-2$ 个数，每个数取出来的时候，结果 要加上 它乘以它左边的再乘以它右边的，也就是 a[i]*a[i-1]*a[i+1]，当然取出后，左右的数据就变化了，题目要求最左端和最右端的两个数不能取，要求选择最合适的顺序去取出这 $n-2$ 个数。
Input
The first line of the input contains the number of cards $N\ (3 \leq N \leq 100)$.
The second line contains $N$ integers in the range from $1$ to $100$, separated by spaces.
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 1 Input
6
10 1 50 50 20 5
Sample 1 Output
3650