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
相关推荐
11-25 17:03
门头沟学院 Java 点赞 评论 收藏
分享
投递小天才等公司10个岗位 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 找工作能把i人逼成什么样 #
15801次浏览 179人参与
# 上班到公司第一件事做什么？ #
110462次浏览 755人参与
# 你今年做了几份实习？ #
10617次浏览 156人参与
# 工作两年想退休了 #
204537次浏览 1813人参与
# 一上班就想____，这正常吗？ #
5823次浏览 100人参与
# 运营面经 #
146208次浏览 1323人参与
# 参加过提前批的机械人，你们还参加秋招么 #
103903次浏览 1641人参与
# 网易求职进展汇总 #
169462次浏览 1414人参与
# 如果公司降薪，你会跳槽吗？ #
111669次浏览 720人参与
# 大厂面试初体验 #
83913次浏览 385人参与
# 金三银四，你有感觉到吗 #
663407次浏览 6032人参与
# 大学最后一个寒假，我想…… #
72476次浏览 727人参与
# 大家每天通勤多久？ #
64646次浏览 415人参与
# 什么样的公司千万别去 #
28358次浏览 149人参与
# 面试尴尬现场 #
206036次浏览 823人参与
# 春招你拿到offer了吗 #
762588次浏览 9777人参与
# 用一句话形容你的团队氛围 #
29241次浏览 248人参与
# 业务面应该做哪些准备 #
79305次浏览 813人参与
# 一起聊华为 #
169041次浏览 822人参与
# 第一份工作应该选高薪还是热爱？ #
141424次浏览 1050人参与