[理工] 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