現在有 N 張數值介於 -10000 ~ 10000 的卡牌,你將可以得到所有卡牌的總和做為收益。
好消息是你有 K 次機會,可以選定一張卡牌施放魔法,改變該卡牌正負號;
也就是由正改負,或由負改正。
當然你也可以將部分魔法集中施放在同張卡牌,則對同張卡牌所施放的魔法兩兩間將互相抵銷。
壞消息是這 K 次魔法都必須確實施放完畢,
也就是即使原本卡牌就已經是正值了,仍必須將 K 次魔法集中或分散施放在某幾張卡牌上。
舉例來說假設 N = 3、K = 1,且三張卡牌分別為 2, 1, 3,
則最佳策略為將魔法施放在數字 1 的卡牌,最大總收益將為 2 + (-1) + 3 = 4。
請協助撰寫一個程式計算最佳策略下,可以得到的最大總收益為何。
第一行有兩個正整數 N 和 K,代表有 N 張卡牌和 K 次魔法需施放
1 ≤ N ≤ 10000
1 ≤ K ≤ N
第二行有 N 個整數 ai,代表第 i 張卡牌原始數字
-10000 ≤ ai ≤ 10000
最佳策略下,可以得到的最大總收益
3 1 2 1 3
4
10%:K = 1
30%:所有 ai 皆為非負整數
60%:無特別限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
41331 |
|
n688 | 71 | 2024-07-17 16:05 |