Re: [理工] 107台大資演對答案

[Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)]

: http://0rz.tw/fLPOZ
: 題目PDF如上

又來問這張考卷>"<

想請問題號V.a.2

題目說要用O(n^2)的時間

以一個雙邊queue(dequeue)製造max alternative sum
--

我的想法是把input sequence先由小到大sort

然後都往dequeue的一邊push進去

最後pop時輪流先從數字大的邊pop 然後小的邊pop 大的邊pop ...

總而言之就是較大的數都是+  較小的數都是-

最後應該可以製造出optimal alternative sum?

而且耗費的時間應該就是O(nlogn)而非題目上限O(n^2)

不知道這樣的想法有沒有瑕疵(至少題目範例可以成功)...謝謝!

※ 引述《Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)》之銘言：
: http://0rz.tw/fLPOZ
: 題目PDF如上
: 想請問關於樹高
: 下面兩題都在問BINARY TREE樹高
: II(8)
: IV(13)
: 台大的考卷有公定ROOT高度是1還是0嗎?
: 有一說法是ROOT層不會有高度 但是眾說紛紜啊@@
: ※ 引述《qscez (天使在身旁 xD)》之銘言：
: : 想討論一下答案
: : I.
: : EDBCA AC
: : II.
: : CBA
: : III.
: : D (討論後更正為B)
: : C
: : IV.
: : CCCC
: : V.
: : (a)
: : (b)
: : (1)
: : S,T stack
: : enque(Q,x){
: :   if S是滿的 return "Q滿"
: :   else push(S,x)
: : }
: : dequeue(Q){
: :   if T空 {
: :     if S空 return "Q空"
: :     else pop(S) into T until S空
: :   }
: :   x = pop(T)
: :   return x
: : }
: : (2)(3)
: : VI.
: : (a) 對Va.Vb 做 Dijkastra Time:O(VlogV+E)
: : (b)
: : (1)
: : (2) 一樣做Dijkastra... Time:O(VlogV+E)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.28.142 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579798052.A.C6A.html
→ cossetannie: 我是先選最大的pop之後再挑最小的pop 然後重複 剛好
→ cossetannie: O(n^2) 你那樣的作法也是可以
→ cossetannie: 不過題目的input應該是一個deque吧?
推 gash55025502: 題目說要對given deque做 你這樣的做法感覺破壞了
→ gash55025502: 原本的deque 而且也不一定能夠在原本的deque做出這
→ gash55025502: 樣的sequence？
→ gash55025502: 一樓的做法不就是題目給的greedy嗎？
推 FRAXIS: 這題應該要 DP 吧
→ cossetannie: 我是挑整個deque的最大最小 題目是看兩個end的元素
→ cossetannie:  先取較大的再取較小的
→ mathtsai: 定義dp[a][b]為從a到b所能得的最大alternative sum
→ mathtsai: dp[a][b] = max{in[a]+dp[a+1][b], in[b]+dp[a][b-1]}
→ mathtsai: 表格: n^2格 ， 每格要查另外兩格得到答案 時間O(n^2)_
→ mathtsai: recurrence、boundary condition還要看現在要加還是減
→ mathtsai: 寫的時候寫仔細點別漏掉就好
→ mathtsai: 題目的deque是給定的，不能改變裡面的順序
→ mathtsai: a的話 隨便給個反例就行了 ex. {5,3,1,2,4}
推 FRAXIS: 你這樣定義 dp[a][b] 要怎麼考慮 alternative?
→ mathtsai: 樓上的疑問是...？定義不清楚嗎？
→ mathtsai: 看dp[a][b]是第幾次要取的數字 來決定這次要加還是減
→ mathtsai: 要減的話 在上面in[a]、in[b]前面加上"-"就好