作者LPH66 ((short)(-15074))
看板C_and_CPP
標題Re: [ACM ] 562
時間Mon Jan 4 00:20:14 2010
※ 引述《loveme00835 (恋さや)》之銘言：
: ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
: ( 未必需要依照此格式，文章條理清楚即可 )
: 題號：562 - http://tinyurl.com/ydxdjcw
: 遇到的問題： Wrong Answer
: 有問題的code : http://nopaste.csie.org/4c438
: 補充說明： 請問大大們我的演算法是不是哪邊出錯了呀 ?
: Q_Q, 如果在看code的時候身體有任何不適, 歡
: 迎批評指教~
這個做法是錯的。
反例: (摘自
http://acm.uva.es/board/viewtopic.php?p=6252#p6252 )
1
5
6 5 5 2 2
它可以被平分 (6+2+2 vs 5+5)
但你的程式會分成 6+5 vs 5+2+2 而輸出 2 (自己跑一次即知)
這類型的題目都不能用 greedy 直接上 通常用的是 dynamic programming
該篇討論串中有討論了一些 ACM 裡的其他類似題 也可以看看
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
→ loveme00835:雖然我的程式在跑6 5 5 2 2結果是 0, 但還是試試DP好 01/04 00:31
→ loveme00835:謝謝大大 01/04 00:34
推 holymars:6 5 2 5 2 這樣去跑就會爆了 01/04 00:35
→ loveme00835:但是我不是邊輸入邊做, 我是輸入完再sorting, 再分 01/04 00:41
→ loveme00835:所以順序都沒差 01/04 00:41
→ loveme00835:2 48 48 49 49 50 50來跑就會錯了 @@ 重寫 01/04 00:49