2014-03-21 22:05

題目：給你N個盒子堆成一座塔，要求下面盒子的長和寬都要嚴格大于上面的。問最多能堆多少個盒子？

解法1：O(n^2)的動態(tài)規(guī)劃解決。其實是最長遞增子序列問題，所以也可以用O(n * log(n))的優(yōu)化算法。

代碼：

// 11.7 n boxes are to stack up to a tower. Every box must be strictly smaller in width and height than the one right below it. // How many boxes at most can you stack up? #include <algorithm> #include <cstdio> #include <vector> using namespace std;struct Box {int x;int y;Box(int _x = 0, int _y = 0): x(_x), y(_y) {};bool operator < (const Box &other) {if (x != other.x) {return x < other.x;} else {return y < other.y;}}; };int main() {vector<Box> v;vector<int> dp;int n;int i, j;int res;while (scanf("%d", &n) == 1 && n > 0) {v.resize(n);for (i = 0; i < n; ++i) {scanf("%d%d", &v[i].x, &v[i].y);}sort(v.begin(), v.end());dp.resize(n);res = 0;for (i = 0; i < n; ++i) {dp[i] = 1;for (j = 0; j < i; ++j) {if (v[j].x < v[i].x && v[j].y < v[i].y) {dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i];}}res = dp[i] > res ? dp[i] : res;}printf("%d\n", res);v.clear();dp.clear();}return 0; }

解法2：用二分查找優(yōu)化后的代碼，其中使用了STL算法庫提供的lower_bound()，二分也不總是要手寫的。

代碼：

1 // 11.7 n boxes are to stack up to a tower. Every box must be strictly smaller in width and height than the one right below it. 2 // How many boxes at most can you stack up? 3 #include <algorithm> 4 #include <cstdio> 5 #include <vector> 6 using namespace std; 7 8 struct Box { 9 int x; 10 int y; 11 Box(int _x = 0, int _y = 0): x(_x), y(_y) {}; 12 13 bool operator < (const Box &other) { 14 if (x != other.x) { 15 return x < other.x; 16 } else { 17 return y < other.y; 18 } 19 }; 20 }; 21 22 int main() 23 { 24 vector<Box> v; 25 vector<int> dp; 26 vector<int>::iterator it; 27 int n; 28 int i; 29 30 while (scanf("%d", &n) == 1 && n > 0) { 31 v.resize(n); 32 for (i = 0; i < n; ++i) { 33 scanf("%d%d", &v[i].x, &v[i].y); 34 } 35 sort(v.begin(), v.end()); 36 dp.push_back(v[0].y); 37 for (i = 1; i < n; ++i) { 38 if (v[i].y > dp[dp.size() - 1]) { 39 dp.push_back(v[i].y); 40 } else { 41 it = lower_bound(dp.begin(), dp.end(), v[i].y); 42 *it = v[i].y; 43 } 44 } 45 printf("%d\n", (int)dp.size()); 46 47 v.clear(); 48 dp.clear(); 49 } 50 51 return 0; 52 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhuli19901106/p/3616836.html

總結(jié)

以上是生活随笔為你收集整理的《Cracking the Coding Interview》——第11章：排序和搜索——题目7的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。