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
相关推荐
点赞 评论 收藏
分享
程序员牛肉：不用，你低估你学历的含金量了。
不用学微服务，重心放到juc，redis和mysql的八股上。然后准备两个简历项目。直接准备明年暑期就好。南京大学都算是国内比较顶尖的985了。明年暑期零实习也能被约面。不用太焦虑 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你觉得面试是靠实力还是靠运气 #
26899次浏览 290人参与
# 哪些公司在招寒假实习？ #
19593次浏览 256人参与
# MiniMax求职进展汇总 #
919次浏览 23人参与
# 秋招遇到的奇葩面试题 #
103075次浏览 421人参与
# 卷__卷不过你们，只能卷__了 #
13736次浏览 311人参与
# 互联网行业现在还值得去吗 #
49327次浏览 362人参与
# 26年哪些行业会变好/更差 #
21055次浏览 311人参与
# 写论文的崩溃时刻 #
7541次浏览 168人参与
# 秋招暂停，我将对以下公司做出处罚__ #
50162次浏览 200人参与
# 去年的flag与今年的小目标 #
11209次浏览 223人参与
# 通信硬件公司爆料 #
186644次浏览 548人参与
# 你不能接受的企业文化有哪些 #
13902次浏览 193人参与
# 有深度的简历长什么样？ #
18047次浏览 368人参与
# 你都用AI做什么 #
7660次浏览 179人参与
# 入职第一天 #
11251次浏览 246人参与
# 关于春招你都做了哪些准备？ #
122343次浏览 709人参与
# 国企vs私企，你更想去？ #
306283次浏览 2494人参与
# 硬件/芯片公司工作体验 #
141941次浏览 939人参与
# 找工作中的小确幸 #
75636次浏览 439人参与
# 大家实习都在做什么？ #
16620次浏览 224人参与
# 招聘要求与实际实习内容不符怎么办 #
149284次浏览 887人参与