D - Add and Remove Editorial /

Time Limit: 2 sec / Memory Limit: 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