关注
如果先做预处理将每层的取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
相关推荐
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
11430次浏览 188人参与
# 牛友的春节生活 #
8780次浏览 173人参与
# 春节前,你还在投简历吗? #
15201次浏览 177人参与
# 备战春招/暑实,现在应该做什么? #
5818次浏览 172人参与
# 牛客AI体验站 #
15085次浏览 268人参与
# 从夯到拉,锐评职场mentor #
5765次浏览 86人参与
# 实习到现在,你最困惑的一个问题 #
5040次浏览 142人参与
# 春节提前走,你用什么理由请假? #
11351次浏览 260人参与
# 距离春招还有一个月,你现在是什么开局? #
7711次浏览 121人参与
# 今年秋招你收到了多少封邮件? #
37863次浏览 279人参与
# 暑期实习什么时候投? #
7853次浏览 181人参与
# 聊聊Agent开发 #
26845次浏览 625人参与
# 机械制造面试记录 #
314148次浏览 3159人参与
# 如何看待offer收割机的行为 #
1038164次浏览 6595人参与
# 推荐一个值得做的AI项目 #
7390次浏览 186人参与
# 非技术投递记录 #
691537次浏览 6857人参与
# 2025,我想...... #
88199次浏览 668人参与
# 找工作,行业重要还是岗位重要? #
96564次浏览 1839人参与
# 我的AI电子员工 #
28361次浏览 192人参与
# 一起聊华为 #
191877次浏览 895人参与

