n688. pC. 卡牌遊戲
Tags : Greedy
Accepted rate : 10人/12人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-15 21:35

Content

現在有 N 張數值介於 -10000 ~ 10000 的卡牌,你將可以得到所有卡牌的總和做為收益。

好消息是你有 K 次機會,可以選定一張卡牌施放魔法,改變該卡牌正負號
也就是由正改負,或由負改正。
當然你也可以將部分魔法集中施放在同張卡牌,則對同張卡牌所施放的魔法兩兩間將互相抵銷。

壞消息是這 K 次魔法都必須確實施放完畢
也就是即使原本卡牌就已經是正值了,仍必須將 K 次魔法集中或分散施放在某幾張卡牌上。

舉例來說假設 N = 3、K = 1,且三張卡牌分別為 2, 1, 3,
則最佳策略為將魔法施放在數字 1 的卡牌,最大總收益將為 2 + (-1) + 3 = 4。

請協助撰寫一個程式計算最佳策略下,可以得到的最大總收益為何。

Input

第一行有兩個正整數 N 和 K,代表有 N 張卡牌和 K 次魔法需施放
1 ≤ N ≤ 10000
1 ≤ K ≤ N

第二行有 N 個整數 ai,代表第 i 張卡牌原始數字
-10000 ≤ ai ≤ 10000

Output

最佳策略下,可以得到的最大總收益

Sample Input #1
3 1
2 1 3
Sample Output #1
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1M
公開 測資點#1 (5%): 2.0s , <1M
公開 測資點#2 (5%): 2.0s , <1M
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1K
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :

10%:K = 1
30%:所有 ai 皆為非負整數
60%:無特別限制 

Tags:
Greedy
出處:
113學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」