← 返回题目列表

AtCoder · agc035_d

D. 添加和删除

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有一堆 N 卡片,每张卡片上都写有一个非负整数。写在上面的整数 i从顶部算起的第一张牌是 A_i.

Snuke将重复以下操作,直到剩下两张牌:

  • 从牌堆中选择三张连续的牌。
  • 吃三张中间的牌。
  • 对于另外两张卡片,将上面写的整数替换为该整数与吃掉的卡片上写的整数之和。
  • 将两张牌放回到牌堆中的原始位置,而不交换它们。

找出最后两张卡片上所写的整数的最小可能总和。

约束

  • 2 \leq N \leq 18
  • 0 \leq A_i \leq 10^9 (1\leq i\leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N

输出

打印最后两张卡片上写入的整数的最小可能总和。


示例输入 1

4
3 1 4 2

示例输出 1

16

我们可以通过执行以下操作来最小化写在最后两张卡片上的整数之和:

  • 最初,写在卡片上的整数是 3, 1, 4,和 2 从上到下。
  • 从顶部选择第一张、第二张和第三张牌。吃第二张牌 上面写着 1 ,加上 将 1 添加到另外两张牌中,然后将它们放回牌堆中的原始位置。现在写在卡片上的整数是 4, 5,和 2 从上到下。
  • 从顶部选择第一张、第二张和第三张牌。吃第二张牌 上面写着 5 ,加上 将 5 添加到另外两张牌中,然后将它们放回牌堆中的原始位置。现在写在卡片上的整数是 9 和 7 从上到下。
  • 剩下的最后两张牌上写的整数之和是 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