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
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你最近因为什么迷茫？ #
11103次浏览 184人参与
# AI coding的好用工具分享 #
3261次浏览 101人参与
# 上班以后，你还有哪些坚持的爱好？ #
1679次浏览 49人参与
# 实习怎么做才有更好的产出 #
2288次浏览 75人参与
# 你都在哪些场所面过试？ #
4439次浏览 79人参与
# 实习生工资多少才算正常？ #
3661次浏览 81人参与
# 你给AI提过哪些离谱的需求？ #
1741次浏览 73人参与
# 实习心态崩了 #
100569次浏览 515人参与
# 找工作以来，你最看不惯__ #
2876次浏览 73人参与
# 领导做过最不靠谱的事 #
4889次浏览 87人参与
# 哪些公司开春招了？ #
1958次浏览 29人参与
# 刚入职就____，这样正常吗？ #
124536次浏览 665人参与
# 秋招有哪些公司要求提前实习 #
102798次浏览 545人参与
# 非技术岗投递进展 #
166666次浏览 1317人参与
# 新年的第一句祝福 #
53616次浏览 389人参与
# 华子oc时间线 #
1408298次浏览 6994人参与
# 当发现同事想辞职 #
13637次浏览 47人参与
# 华为保温 #
169699次浏览 642人参与
# 实习转正进行时 #
138802次浏览 897人参与
# 拿到offer之后，可以做些什么 #
85388次浏览 442人参与