关注
如果先做预处理将每层的取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
相关推荐
查看8道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
1786次浏览 24人参与
# 聊聊Agent开发 #
7052次浏览 184人参与
# 春节前,你还在投简历吗? #
3331次浏览 38人参与
# 推荐一个值得做的AI项目 #
2219次浏览 66人参与
# 你的房租占工资的比例是多少? #
84930次浏览 873人参与
# 春节提前走,你用什么理由请假? #
1533次浏览 31人参与
# 你上一次给父母打电话是什么时候 #
35295次浏览 246人参与
# 每个月的工资都是怎么分配的? #
85695次浏览 672人参与
# 距离春招还有一个月,你现在是什么开局? #
1629次浏览 29人参与
# 暑期实习什么时候投? #
2238次浏览 44人参与
# 你认为哪个岗位找工作最卷 #
61764次浏览 250人参与
# 新年的第一句祝福 #
56222次浏览 393人参与
# 实习想申请秋招offer,能不能argue薪资 #
218056次浏览 1167人参与
# 工作一周年分享 #
51560次浏览 272人参与
# 非技术2023笔面经 #
332223次浏览 2711人参与
# 一份好的简历长什么样? #
25106次浏览 447人参与
# 考公VS就业,你怎么选? #
92434次浏览 514人参与
# 你觉得机械有必要实习吗 #
73833次浏览 489人参与
# 汇川技术求职进展汇总 #
179596次浏览 1058人参与
# 简历当中有水分算不算造假? #
159329次浏览 2265人参与
