首页 > 代码库 > POJ 3628 Bookshelf 2 题解
POJ 3628 Bookshelf 2 题解
本题解法很多,因为给出的数据特殊性故此可以使用DFS和BFS,也可以使用01背包DP思想来解。
因为一般大家都使用DFS,这里使用很少人使用的BFS,缺点是比DFS更加耗内存,不过优点是速度比DFS快。
当然也比DFS难写点:
int N, B; int Height[21]; inline int mMin(int a, int b) { return a > b? b : a; } inline int mMax(int a, int b) { return a < b? b : a; } int bfs() { vector<int> vStk; vStk.push_back(0); int id = 0; int mh = INT_MAX; while (id < N) { for (int i = (int)vStk.size() - 1; i >= 0 ; i--) { int h = vStk[i] + Height[id]; if (h >= B) mh = mMin(mh, h-B); vStk.push_back(h); }//缺点,会消耗大量的内存,最后vector会非常大,优点,速度比dfs快 id++; } return mh; } int main() { while (scanf("%d %d", &N, &B) != EOF) { for (int i = 0; i < N; i++) { scanf("%d", &Height[i]); } printf("%d\n", bfs()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。