回分類題庫
z084: B. 吊飾
關鍵字: NPSC2018決賽、2019模擬-F

測資點 : 10 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 0 Times / 0 Users | Submit : 0 Times / 0 Users | Accepted rate : 0%
題目加入時間 : 2019-11-11 23:04

Content: 简体中文

小Y 和小P 是兩個特殊的國中生,他們都喜歡玩吊飾。他們玩吊飾的方法也很特別:他們喜歡用許多環把許多小吊飾串起來,做成一個十分獨特的飾品。
經過一段時間的研究後,他們發現他們所用來串起小吊飾的環可以分為兩大類:「Y 環」和
「P 環」。這兩類的環在外觀和功能性上都有所不同,要適當的搭配兩種環才能做出好看的飾品。
某一天小Y 和小P 想要用N 個小吊飾組合出一個新的飾品。他們希望這個飾品可以吊起來,所以他們決定用以下三個規則來做出這個飾品:
1. 飾品的最上面是一個Y 環。
2. 每個小吊飾和環,除了最上面的那個Y 環以外,都會串在另外一個環的下面。
3. 每個環的下面必須從兩種串法擇一:一是串一個小吊飾,二是串一或兩個環,但是不能串兩個相同類型的環(也就是說,如果串的是兩個環的話,必須要是Y 環和P 環各一個)。

當然,就算有這三個規則,還是有很多不同的組合方式。因此,小Y 和小P 為每個小吊飾和環都打了一個「美觀度」的分數,其中所有Y 環的美觀度都相同,所有P 環的美觀度也都相同。
小Y 和小P 認為一個飾品最重要的是整體的美感。因此,他們認為整個飾品的「不平衡度」
應該愈小愈好。一個飾品的不平衡度是每個小吊飾不平衡度的加總,而一個小吊飾的不平衡度是該小吊飾上面所有環美觀度的加總,乘上該小吊飾本身的美觀度。
然而,小Y 和小P 雖然嘗試了許多不錯的組合方式,但是一直沒辦法確定有沒有更好的方式。因此,請你寫一個程式幫他們算出以這N 個小吊飾組成的飾品,不平衡度最小可以是多
少。
 

Input:

輸入的第一行包含三個正整數 N , a , b,依序代表總小吊飾數量、「Y 環」的美觀度和「P 環」的美觀度。
第二行包含 N 個以空白隔開的正整數 xi,代表每個小吊飾的美觀度。
• N ≤ 15
• a , b , xi ≤ 108

Output:

請輸出一行包含一個正整數,代表這些小吊飾組合成的飾品的不平衡度最小可以是多少。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3 3 7
1 3 5

Sample Output :

86

Hint :

Author :

NPSC2018決賽、2019模擬-F (管理員:Chang)

  Solve it!   Status Forum