作者pokia (幻影成風)
看板C_and_CPP
標題Re: [ACM ] 714 WA (updated)
時間Tue Nov 3 22:40:14 2009
※ 引述《pokia (幻影成風)》之銘言：
: http://acm.uva.es/p/v7/714.html
: My code: http://nopaste.info/2bc3437c51.html
: 現在一直WA了...
: 不知道演算法有沒有錯...
: 還是output那邊有問題
: 自己測了好多測資都沒問題...所以也不知道還有什麼bug
最近把這題拿出來重寫...
想用dynamic programming的方式
不過題目給的條件好像不符合suboptimal的特性?
例如: 10 2 10 2 15 20 30
以DP來解會得到
10 / 2 10 2 15 / 20 1 / 30
但實際答案是
10 2 10 / 2 15 / 20 1 / 30
因為題目的這一句:
If there is more than one solution,
print the one that minimizes the work assigned to the first scriber,
then to the second scriber etc.
其實在做
10 2 10 2 15 時
正確答案會得到 10 / 2 10 2 15
maxsum = (10,2+10+2+15) =
29
但suboptimal 10 2 10 / 2 15
maxsum = (10+2+10,2+15) =
22
好像違反了suboptimal的特性??
所以這題是不是沒辦法用DP解
只能binary search嗎??
還是要加上什麼條件呢??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.245.19
1F：推 DJWS:你得先確定你找出的recurrence是正確的 11/04 09:35
2F：→ DJWS:如果發現不對 那就要再找另外一種recurrence 11/04 09:36
3F：推 ledia:DP 應該是沒問題的, 他的條件只是 backtrack 時的 tie break 11/04 11:21
4F：推 DJWS:切子問題可以從左端切掉 不要從右端切掉 事情會簡單得多 11/04 12:15
5F：→ pokia:AC了...用DP O(n^3)的方式明顯很慢... 11/04 22:54
6F：→ pokia:最後只能用greedy的方式來求'/'的擺放位置 11/04 22:55
7F：推 DJWS:DP或許能再加速 就像optimal binary search tree的O(N^2) 11/05 09:11
8F：→ DJWS:另外'/'的位置沒必要用greedy來求 recurrence設計的夠好就行 11/05 10:11
9F：→ DJWS:以前有寫過 但是code沒留下 不知道印象對不對 11/05 10:12