/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1000 点
問題文
非負整数のひとつ書かれたカードが N 枚積まれた山があります。上から i 番目のカードに書かれた整数は A_i です。
すぬけ君は、以下の操作をカードが 2 枚になるまで繰り返します。
- 連続して積まれている 3 枚のカードを選ぶ。
- 3 枚のうち真ん中のカードを食べる。
- あとの 2 枚のカードに書かれている整数を、その整数に食べたカードに書かれていた整数を足してできる整数に書き換える。
- 食べなかった 2 枚のカードを、順序を保ったまま山のもとの位置に戻す。
最終的に残る 2 枚のカードに書かれた整数の和の最小値を求めてください。
制約
- 2 \leq N \leq 18
- 0 \leq A_i \leq 10^9 (1\leq i\leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
最終的に残る 2 枚のカードに書かれた整数の和の最小値を出力せよ。
入力例 1
4 3 1 4 2
出力例 1
16
以下の操作を行うことで、最終的に残る 2 枚のカードに書かれた整数の和を最小にできます。
- 最初、カードに書かれた整数は順に 3,1,4,2 である。
- 1,2,3 番目のカードを選ぶ。1 の書かれた 2 枚目のカードを食べ、残ったカードに書かれた整数に 1 を足し、山のもとの位置に戻す。カードに書かれた整数は順に 4,5,2 となる。
- 1,2,3 番目のカードを選ぶ。5 の書かれた 2 枚目のカードを食べ、残ったカードに書かれた整数に 5 を足し、山のもとの位置に戻す。カードに書かれた整数は順に 9,7 となる。
- 最後に残った 2 枚のカードに書かれた整数の和は 16 になる。
入力例 2
6 5 2 4 1 6 9
出力例 2
51
入力例 3
10 3 1 4 1 5 9 2 6 5 3
出力例 3
115
Score : 1000 points
Problem Statement
There is a stack of N cards, each of which has a non-negative integer written on it. The integer written on the i-th card from the top is A_i.
Snuke will repeat the following operation until two cards remain:
- Choose three consecutive cards from the stack.
- Eat the middle card of the three.
- For each of the other two cards, replace the integer written on it by the sum of that integer and the integer written on the card eaten.
- Return the two cards to the original position in the stack, without swapping them.
Find the minimum possible sum of the integers written on the last two cards remaining.
Constraints
- 2 \leq N \leq 18
- 0 \leq A_i \leq 10^9 (1\leq i\leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the minimum possible sum of the integers written on the last two cards remaining.
Sample Input 1
4 3 1 4 2
Sample Output 1
16
We can minimize the sum of the integers written on the last two cards remaining by doing as follows:
- Initially, the integers written on the cards are 3, 1, 4, and 2 from top to bottom.
- Choose the first, second, and third card from the top. Eat the second card with 1 written on it, add 1 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 4, 5, and 2 from top to bottom.
- Choose the first, second, and third card from the top. Eat the second card with 5 written on it, add 5 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 9 and 7 from top to bottom.
- The sum of the integers written on the last two cards remaining is 16.
Sample Input 2
6 5 2 4 1 6 9
Sample Output 2
51
Sample Input 3
10 3 1 4 1 5 9 2 6 5 3
Sample Output 3
115