关注
第四题是dp题:例如
6 4
1 4 3 7 6 2
题解如下:
1.首先删除4个数等价于留下2个数。
2.跟数组顺序无关,因此先将数组排序成:1 2 3 4 6 7
3.枚举每个元素a比其大的且成倍数关系的元素,例如:
1有{2,3,4,6,7}
2有{2,4,6}
3有{6}
4有{}
6有{}
7有{}
4.推导状态转移方程,先思考留下1个数,当留下1个数的时候,dp[i][1]的方案数都等于1。留下2个数,对于每一个元素,只要累加比其大且成倍数关系的元素j的dp[j][2-1]即可。此时dp[1][2]等于5、dp[2][2]等于3、dp[3][2]等于1,其余元素都是0,将其加起来就是8,就等于方案数。依次类推到n,时间复杂度O(n^2)。
查看原帖
1 评论
相关推荐
04-16 10:50
北京理工大学 前端开发其它 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 简历上如何体现你的“AI”能力? #
11412次浏览 266人参与
# 正在春招的你,也参与了去年秋招吗? #
397464次浏览 2736人参与
# 华泰星战营,提前锁定校招offer #
12535次浏览 382人参与
# 哪些AI项目值得做? #
21303次浏览 531人参与
# 实习要如何选择和准备? #
157786次浏览 1584人参与
# 找不到大厂实习可以去小厂吗? #
16767次浏览 193人参与
# 虾皮求职进展汇总 #
402062次浏览 2867人参与
# 你总挂在第__面? #
8142次浏览 90人参与
# 非技术岗薪资爆料 #
529031次浏览 3095人参与
# 实习时最怕听到的一句话 #
18820次浏览 172人参与
# 没有面试的日子里,你在做什么 #
10837次浏览 324人参与
# 你简历上最心虚的一句话 #
17561次浏览 212人参与
# 90后北漂现状 #
38956次浏览 225人参与
# 京东笔试 #
172087次浏览 935人参与
# 你知道最慷慨和最抠的公司分别是 #
9020次浏览 73人参与
# 25届嵌入式真的回暖了吗 #
52432次浏览 385人参与
# 父母对你找工作是助力还是阻力? #
46204次浏览 405人参与
# 非技术投递记录 #
726715次浏览 6948人参与
# 刚入职就____,这样正常吗? #
141306次浏览 685人参与
# 拼多多工作体验 #
57751次浏览 418人参与
# 参加哪些竞赛对找工作有帮助? #
47634次浏览 250人参与
查看13道真题和解析