[理工] 109交大 資演

[lucy35 ()]

http://i.imgur.com/331bMsz.jpg

請問第九題（24,25,26）要怎麼答題比較好
想了很多次還是不知道怎麼找滿足的條件

謝謝

-----
Sent from JPTT on my Samsung SM-A715F.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.222.200 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1610728182.A.973.html
→ mathtsai: 25.按照題目給的條件 簡單不等式就能寫
→ mathtsai: 26.根據題目給的定義
→ mathtsai: prefix_sum[i] is at most s 所以遞迴選C
→ mathtsai: D應該是 D(n, min(6an,sum of A))
→ mathtsai: E 表格大小決定dp複雜度 表格大小最多n*6an
→ mathtsai: 我記得這題好像前面也有，可以找找
→ mathtsai: 24.是說順序不能變 暴力找應該都是5個
請問是哪五個咧？
→ mathtsai: D 應該是 D(n,sum of A)
→ mathtsai: E 我要再想想 不太清楚為啥不是表格大小
推 joywilliamjo: 24 subsequence不能拆著或跳號，他舉例應該是故意舉
→ joywilliamjo: 全部一樣的不然24題太送分= =
推 joywilliamjo: 25應該沒啥問題的，每個選項帶進去湊還比較快
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/16/2021 13:22:50
推 jordan1997: 24應該是（2，5，3，2，2）
推 joywilliamjo: 或36212
推 jordan1997: 3，6，2，1，2不會對，因為3+6+2>6*1
推 sevfouyu11: 所以這題subsequence是不用連號的吧？
→ sevfouyu11: 因為如果要連號的話就最多只能(2,5,3,6)，k=4
→ sevfouyu11: 取36212的話就像樓上說的在1的地方會不合
→ mathtsai: 看題目 不用連號
推 joywilliamjo: 對= =我看錯了以為可以到K，感謝提醒
感謝樓上們講解
我了解運作了！！
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/17/2021 00:11:15
※ 編輯: lucy35 (42.77.222.200 臺灣), 01/17/2021 00:11:52
推 cstease64: E n*6{an}  = O(n{an})