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
相关推荐
查看2道真题和解析
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 赚钱的意义在这一刻具象化 #
2661次浏览 69人参与
# 哪些瞬间让你真切感受到了工作的乐趣 #
23056次浏览 98人参与
# 今年春招是金一银二嘛？ #
3356次浏览 48人参与
# AI求职实录 #
1636次浏览 51人参与
# 1月小结：你过的开心吗？ #
823次浏览 28人参与
# 你的第一家实习公司是什么档次？ #
2460次浏览 45人参与
# 抛开难度不谈，你最想去哪家公司？ #
1925次浏览 61人参与
# 为什么有人零实习也能进大厂？ #
2802次浏览 67人参与
# AI时代的工作 VS 传统时代的工作，有哪些不同？ #
5654次浏览 136人参与
# 你的landing期是如何度过的？ #
5548次浏览 96人参与
# 工作后会跟朋友渐行渐远吗 #
57669次浏览 411人参与
# 除了Java，最推荐学什么技术？ #
3976次浏览 112人参与
# 当你问AI“你会取代我的工作吗”，它说_？ #
2018次浏览 77人参与
# 汇川技术求职进展汇总 #
177595次浏览 1055人参与
# 我是XXX，请攻击我最薄弱的地方 #
55530次浏览 387人参与
# 选offer应该考虑哪些因素 #
139799次浏览 983人参与
# 你觉得什么岗位会被AI替代 #
36066次浏览 246人参与
# 如果工作一直消耗情绪还要继续做吗 #
18486次浏览 88人参与
# 你上一次加班是什么时候？ #
128831次浏览 737人参与
# 非技术岗简历怎么写 #
284031次浏览 3185人参与