[理工] 109交大 資演

作者: lucy35 (肥宅系社花)   2021-01-16 00:29:38
http://i.imgur.com/331bMsz.jpg
請問第九題(24,25,26)要怎麼答題比較好
想了很多次還是不知道怎麼找滿足的條件
謝謝
作者: mathtsai (mathtsai)   2021-01-16 01:32:00
25.按照題目給的條件 簡單不等式就能寫26.根據題目給的定義prefix_sum[i] is at most s 所以遞迴選CD應該是 D(n, min(6an,sum of A))E 表格大小決定dp複雜度 表格大小最多n*6an我記得這題好像前面也有,可以找找24.是說順序不能變 暴力找應該都是5個D 應該是 D(n,sum of A)E 我要再想想 不太清楚為啥不是表格大小
作者: joywilliamjo (joywilliamjoy)   2021-01-16 10:15:00
24 subsequence不能拆著或跳號,他舉例應該是故意舉全部一樣的不然24題太送分= =25應該沒啥問題的,每個選項帶進去湊還比較快
作者: jordan1997 (allenwalker)   2021-01-16 17:36:00
24應該是(2,5,3,2,2)
作者: joywilliamjo (joywilliamjoy)   2021-01-16 19:35:00
或36212
作者: jordan1997 (allenwalker)   2021-01-16 19:47:00
3,6,2,1,2不會對,因為3+6+2>6*1
作者: sevfouyu11 (sevfouyu11)   2021-01-16 20:50:00
所以這題subsequence是不用連號的吧?因為如果要連號的話就最多只能(2,5,3,6),k=4取36212的話就像樓上說的在1的地方會不合
作者: mathtsai (mathtsai)   2021-01-16 21:39:00
看題目 不用連號
作者: joywilliamjo (joywilliamjoy)   2021-01-16 23:54:00
對= =我看錯了以為可以到K,感謝提醒
作者: cstease64 (clk)   2021-01-22 23:33:00
E n*6{an} = O(n{an})

Links booklink

Contact Us: admin [ a t ] ucptt.com