作者lucy35 ()
看板Grad-ProbAsk
標題[理工] 109交大 資演
時間Sat Jan 16 00:29:38 2021
http://i.imgur.com/331bMsz.jpg
請問第九題（24,25,26）要怎麼答題比較好
想了很多次還是不知道怎麼找滿足的條件
謝謝
-----
Sent from JPTT on my Samsung SM-A715F.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.222.200 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1610728182.A.973.html
1F：→ mathtsai: 25.按照題目給的條件 簡單不等式就能寫 01/16 01:32
2F：→ mathtsai: 26.根據題目給的定義 01/16 01:33
3F：→ mathtsai: prefix_sum[i] is at most s 所以遞迴選C 01/16 01:34
4F：→ mathtsai: D應該是 D(n, min(6an,sum of A)) 01/16 01:35
5F：→ mathtsai: E 表格大小決定dp複雜度 表格大小最多n*6an01/16 01:36
6F：→ mathtsai: 我記得這題好像前面也有，可以找找01/16 01:40
7F：→ mathtsai: 24.是說順序不能變 暴力找應該都是5個01/16 01:44
請問是哪五個咧？
8F：→ mathtsai: D 應該是 D(n,sum of A)01/16 01:49
9F：→ mathtsai: E 我要再想想 不太清楚為啥不是表格大小01/16 01:52
10F：推 joywilliamjo: 24 subsequence不能拆著或跳號，他舉例應該是故意舉01/16 10:15
11F：→ joywilliamjo: 全部一樣的不然24題太送分= =01/16 10:15
12F：推 joywilliamjo: 25應該沒啥問題的，每個選項帶進去湊還比較快01/16 10:18
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/16/2021 13:22:50
13F：推 jordan1997: 24應該是（2，5，3，2，2）01/16 17:36
14F：推 joywilliamjo: 或3621201/16 19:35
15F：推 jordan1997: 3，6，2，1，2不會對，因為3+6+2>6*101/16 19:47
16F：推 sevfouyu11: 所以這題subsequence是不用連號的吧？01/16 20:50
17F：→ sevfouyu11: 因為如果要連號的話就最多只能(2,5,3,6)，k=401/16 20:50
18F：→ sevfouyu11: 取36212的話就像樓上說的在1的地方會不合01/16 20:51
19F：→ mathtsai: 看題目 不用連號01/16 21:39
20F：推 joywilliamjo: 對= =我看錯了以為可以到K，感謝提醒 01/16 23:54
感謝樓上們講解
我了解運作了！！
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/17/2021 00:11:15
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/17/2021 00:11:52
21F：推 cstease64: E n*6{an} = O(n{an}) 01/22 23:33