Re: [ACM ] 714 WA (updated)
※ 引述《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
推
11/04 09:35, , 1F
11/04 09:35, 1F
→
11/04 09:36, , 2F
11/04 09:36, 2F
推
11/04 11:21, , 3F
11/04 11:21, 3F
推
11/04 12:15, , 4F
11/04 12:15, 4F
→
11/04 22:54, , 5F
11/04 22:54, 5F
→
11/04 22:55, , 6F
11/04 22:55, 6F
推
11/05 09:11, , 7F
11/05 09:11, 7F
→
11/05 10:11, , 8F
11/05 10:11, 8F
→
11/05 10:12, , 9F
11/05 10:12, 9F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
