作者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/cn.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