看板 [ Math ]
討論串[其他] 一題 Codeforces 取硬幣演算法反例證明
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#3
Re: [其他] 一題 Codeforces 取硬幣演算法反例證明
推噓2(2推 0噓 17→)留言19則，0人參與, 4年前最新作者alan23273850 (God of Computer Science)時間4年前 (2021/02/16 19:26), 4年前編輯資訊
0
0
2
內容預覽:
我再幫這篇貼文增補一張更平易近人的示意圖，以驗證我自己的理解！. 在 X+Y 之前的硬幣因為組態沒有改變，所以選擇的組合也不會改變，這很自然。. .......______...●...●... implies f(A) + Ｘ + Ｙ <= S. A Ｘ Ｙ. .......[●●]... sin
(還有822個字)
#2
Re: [其他] 一題 Codeforces 取硬幣演算法反例證明
推噓1(1推 0噓 2→)留言3則，0人參與, 4年前最新作者LPH66 ( )時間4年前 (2021/02/16 01:12), 編輯資訊
0
0
2
內容預覽:
他的邏輯是這樣的:. 如果被加入的硬幣最大的兩個的幣值是 x 和 y, x≧y. 當然這兩個硬幣會被選 (不然就不用加了). 那把這兩個硬幣換成一個 x+y 的話. (1) x+y 大於 x, 所以貪心法一定會比選 x 時更早選走 x+y. 那麼在新組合的貪心法的過程中, 到同樣硬幣時已選總錢數一定
(還有518個字)
#1
[其他] 一題 Codeforces 取硬幣演算法反例證明
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者alan23273850 (God of Computer Science)時間4年前 (2021/02/15 21:42), 編輯資訊
0
0
2
內容預覽:
小弟今天正在練習這題 https://codeforces.com/problemset/problem/725/E. 解答如下 https://codeforces.com/blog/entry/47974 (第 E 題). 題目是想用增加冗餘硬幣的方式證明 "貪心法 (優先取大) 取硬幣" 並不
(還有338個字)
首頁
上一頁
1
下一頁
尾頁