作者Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)
看板Grad-ProbAsk
標題Re: [理工] 107台大資演對答案
時間Fri Jan 24 00:47:29 2020
: 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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579798052.A.C6A.html
1F：→ cossetannie: 我是先選最大的pop之後再挑最小的pop 然後重複 剛好 01/24 01:34
2F：→ cossetannie: O(n^2) 你那樣的作法也是可以 01/24 01:34
3F：→ cossetannie: 不過題目的input應該是一個deque吧? 01/24 01:38
4F：推 gash55025502: 題目說要對given deque做 你這樣的做法感覺破壞了 01/24 12:03
5F：→ gash55025502: 原本的deque 而且也不一定能夠在原本的deque做出這 01/24 12:03
6F：→ gash55025502: 樣的sequence？ 01/24 12:03
7F：→ gash55025502: 一樓的做法不就是題目給的greedy嗎？ 01/24 12:04
8F：推 FRAXIS: 這題應該要 DP 吧 01/24 12:34
9F：→ cossetannie: 我是挑整個deque的最大最小 題目是看兩個end的元素 01/24 13:30
10F：→ cossetannie: 先取較大的再取較小的 01/24 13:30
11F：→ mathtsai: 定義dp[a][b]為從a到b所能得的最大alternative sum 01/25 02:58
12F：→ mathtsai: dp[a][b] = max{in[a]+dp[a+1][b], in[b]+dp[a][b-1]} 01/25 03:00
13F：→ mathtsai: 表格: n^2格 ， 每格要查另外兩格得到答案 時間O(n^2)_ 01/25 03:01
14F：→ mathtsai: recurrence、boundary condition還要看現在要加還是減 01/25 03:02
15F：→ mathtsai: 寫的時候寫仔細點別漏掉就好 01/25 03:03
16F：→ mathtsai: 題目的deque是給定的，不能改變裡面的順序 01/25 03:04
17F：→ mathtsai: a的話 隨便給個反例就行了 ex. {5,3,1,2,4} 01/25 03:07
18F：推 FRAXIS: 你這樣定義 dp[a][b] 要怎麼考慮 alternative? 01/25 12:32
19F：→ mathtsai: 樓上的疑問是...？定義不清楚嗎？ 01/25 14:48
20F：→ mathtsai: 看dp[a][b]是第幾次要取的數字 來決定這次要加還是減 01/25 14:49
21F：→ mathtsai: 要減的話 在上面in[a]、in[b]前面加上"-"就好 01/25 14:51