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
相关推荐
点赞 评论 收藏
分享
2025-12-30 17:58
Conservatoire National Supérieur Musique et Dance de Lyon Java 点赞 评论 收藏
分享
上海得物信息集团有限公司公司福利 1263人发布 牛客热帖
更多
正在热议
更多
# 哪些公司在招寒假实习？ #
12625次浏览 156人参与
# 卷__卷不过你们，只能卷__了 #
10355次浏览 226人参与
# MiniMax求职进展汇总 #
634次浏览 23人参与
# 26年哪些行业会变好/更差 #
17156次浏览 227人参与
# 写论文的崩溃时刻 #
5395次浏览 128人参与
# 去年的flag与今年的小目标 #
8676次浏览 179人参与
# 有深度的简历长什么样？ #
15369次浏览 319人参与
# 你不能接受的企业文化有哪些 #
10512次浏览 154人参与
# 入职第一天 #
9316次浏览 196人参与
# 你都用AI做什么 #
6169次浏览 144人参与
# 国企vs私企，你更想去？ #
305228次浏览 2485人参与
# 一人分享一道面试手撕题 #
20663次浏览 743人参与
# 你在职场上见过哪些“水货”同事 #
29066次浏览 162人参与
# 机械人还在等华为开奖吗？ #
304823次浏览 1553人参与
# 关于春招你都做了哪些准备？ #
122086次浏览 704人参与
# 机械人的秋招小目标 #
26038次浏览 229人参与
# 你怎么看待AI面试 #
133220次浏览 742人参与
# 现在前端的就业环境真的很差吗 #
492164次浏览 5964人参与
# 晒一晒你收到的礼盒 #
95147次浏览 462人参与
# 找工作时的取与舍 #
115044次浏览 848人参与
# 实习，不懂就问 #
149704次浏览 1340人参与