sky游荡
2020-07-28 13:46 南京邮电大学 C++
关注
如果先做预处理将每层的取j个的最优情况 放在vector<vector<int>>value;中，
value[i][j]代表在第i层取j个的最优解，做出这样的二维数组，时间复杂度是O(100*10000)；每一层是O（10000），最多100层，
然后可以用动态规划。 dp[i][j] 表示到第i层，取j个，的最优解，
那么dp[i][j]等于，dp[i-1][j-x]+value[i][x];x是0->j;就是前面用0个，这层用j个，前面用1个这层用j-1个。。。的最优解，
然后时间复杂度是 O(100*100*100),第一个是一共100层，第二个是 j最多取道100个，第三个是从 0-j,1-j-1...j-0;一共比较100次。
所以最后的时间复杂度是O(1百万)；
欢迎指正。
查看原帖
点赞 3
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
04-27 19:35
萍乡学院 后端工程师 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# AI让海力士市值突破9000亿美元 #
399次浏览 7人参与
# 百度工作体验 #
335848次浏览 2285人参与
# 在爱玛，骑向未来 #
46653次浏览 443人参与
# 牛油的搬砖plog #
202931次浏览 1305人参与
# 职场新人体验 #
193470次浏览 1257人参与
# 机械笔面试考察这些知识点 #
20328次浏览 151人参与
# 秋招感动瞬间 #
126480次浏览 568人参与
# 工作后，你落下了哪些病根 #
42740次浏览 302人参与
# 90后北漂现状 #
40904次浏览 227人参与
# 米哈游求职进展汇总 #
692326次浏览 3364人参与
# 机械/制造每日一题 #
98146次浏览 1503人参与
# 机械人，说说你的烦心事 #
149374次浏览 1176人参与
# 百度求职进展汇总 #
732052次浏览 6452人参与
# 工作压力大，你会干什么？ #
83134次浏览 717人参与
# 机械人与华为的爱恨情仇 #
160818次浏览 1059人参与
# 重来一次，我还会选择这个专业吗 #
468112次浏览 3988人参与
# 打工人的精神状态 #
155405次浏览 1574人参与
# 什么专业适合考公 #
70058次浏览 364人参与
# 面试被问第一学历差时该怎么回答 #
293811次浏览 2299人参与
# 机械人，秋招第一次笔试的企业是哪家？ #
103893次浏览 709人参与
# 实习生工资多少才算正常？ #
78336次浏览 540人参与