回分類題庫
z026: 吃吃為吃吃,是吃也
關鍵字: npsc 2017模擬試題

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 7 Times / 6 Users | Submit : 12 Times / 7 Users | Accepted rate : 86%
題目加入時間 : 2018-10-04 11:43

Content: 简体中文

喜歡做點⼼餵⾷⼩蘿莉的蘿莉農為了精進他的廚藝,特地從世界各地收集了n 特級⾷材。他打算從中挑選⼀些⾷材製作成特級餅乾,之後裝進他親⼿製作的精美餅乾盒中。但要挑選哪些⾷材好呢?蘿莉農覺得他必須親⾃嚐過所有可能的⾮空⾷材組合,才有辦法從這 2n 1 種組合中挑出最適合蘿莉⾷⽤的餅乾。

我們知道,有些⾷材是天⽣絕配,搭在⼀起會有額外的好吃度加成;⽽有些⾷材如果混在⼀起的話反⽽會有反效果,甚⾄是⾷物中毒。更精確地來說,⼀個⾷材搭配是⼀個集合 s 以及⼀個好吃度影響值 v,如果挑選的⾷材組合包含 s 的話,其好吃度就會加上 v。也就是說⼀個⾷材組合的好吃度,就是其所有包含的⾷材搭配的好吃度總和。舉例來說,如果⾷材搭配 {1,2} 的好吃度影響值是 3,⽽⾷材搭配 {2,3} 的好吃度影響值是 1,那麼⾷材組合 {1,2,3} 的好吃度就是 3 + (1) = 2

蘿莉農嘗試各種組合的同時,他的廚藝熟練度也會逐漸上升。因此若第 i 次的⾷材組合好吃度是 d,則製作出來的餅乾好吃度會是 i×d。為了讓這個試嚐餅乾的過程盡量愉悅⽽不要從此對餅乾有⼼理陰影,他希望找⼀個最好的組合嘗試順序,讓做出來的餅乾總好吃度最⼤。

以上⾯的例⼦來說,⼀種可能的最好嘗試順序為{2,3},{1},{2},{3},{1,3},{1,2,3},{1,2},其總好吃度為1 + 2×0 + 3×0 + 4×0 + 5×0 + 6×2 + 7×3 = 32

Input:

測試資料第⼀⾏有兩個正整數n,m,分別代表⾷材數跟⾷材搭配數。接下來 m ⾏,每⾏會有⼀個字串 si 跟⼀個整數 vi

如果 si 的第 j 個字元是 1 的話代表此搭配中包含第 j 種⾷材;反之若為 0 的話則代表不包含。⽽ vi 則為此搭配的好吃度影響值。

• 1 n 22
1 m 105
|si| = n
si 中⾄少有⼀個字元為 1
所有的 si 皆相異
100 vi +100

Output:

請輸出⼀個整數於⼀⾏,代表最好嘗試順序的總好吃度。

Sample Input:help

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

Sample Output :

2

Hint :

Author :

npsc 2017模擬試題 (管理員:Chang)

  Solve it!   Status Forum