[ARC029A] 高橋君とお肉
题意翻译
高桥君和他的朋友一起露营。
高桥君有两个性能相同的烤肉机。这两个烤肉机可以一起工作。一旦把肉放上了烤肉机,就不能中途把肉拿下来,而且你不能同时在一个烤肉机上烤两块肉,也不能把一块烤肉放在两个烤肉机上。直到肉烤好,你才可以把肉取出来。
总共有N块肉,肉的编号为1~N,烤第i块肉所欲的时间为ti。不计算把肉放进烤肉机和拿出烤肉机的时间。
高桥君是一个肉食爱好者,他要求把所有的肉都烤完,而且因为大家的肚子都饿了,所以让烤肉的时间尽可能的最短。
请你求出烤完这些肉的最短时间。
输入输出格式:
输入: 第一行一个整数N(1≤N≤4)
接下来N行,每行是烤第i块肉的所需的时间ti(1≤ti≤50)。
输出格式:
一行,表示所需的最短的时间。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc029/tasks/arc029_1
高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである $ 2 $ 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。$ 2 $ つの肉焼き器にまたがって $ 1 $ つのお肉を置くことはできない。また、お肉は全部で $ N $ 個あり、お肉には $ 1 $ から $ N $ まで番号が付けられている。お肉 $ i $ を焼くのには、どちらの肉焼き器でも時間 $ t_i $ だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。
高橋君はお肉を焼く係であり、$ N $ 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。
すべてのお肉を焼くのにかかる時間の最小値を求めよ。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ t_1 $ $ t_2 $ : $ t_N $
- $ 1 $ 行目には、お肉の個数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 4) $ が与えられる。これは、お肉が $ N $ 個あることを表す。
- $ 2 $ 行目から $ N $ 行にはお肉の情報が与えられる。$ N $ 行のうち $ i $ 行目には整数 $ t_i $ が書かれており、これはお肉 $ i $ を焼くのにかかる時間が $ t_i\ (1\ ≦\ t_i\ ≦\ 50) $ であることを表す。
输出格式
すべてのお肉を焼くのにかかる時間の最小値を $ 1 $ 行に出力せよ。出力の末尾にも改行を入れること。
输入输出样例
输入样例 #1
4
4
6
7
10
输出样例 #1
14
输入样例 #2
3
1
2
4
输出样例 #2
4
输入样例 #3
1
29
输出样例 #3
29
说明
### Sample Explanation 1
一方の肉焼き器でお肉 $ 1 $ とお肉 $ 4 $ を、他方の肉焼き器でお肉 $ 2 $ とお肉 $ 3 $ を順に焼きます (下の図は参考図)。 !\[\](/img/arc/029/1-1.png)
### Sample Explanation 2
一方の肉焼き器でお肉 $ 3 $ を焼いている間に、他方の肉焼き器で残りすべてのお肉を焼きます。