做网站开发要学什么,品牌设计公司简介,网站佣金怎么做分录,不需要备案的服务器2014-03-21 22:05 题目#xff1a;给你N个盒子堆成一座塔#xff0c;要求下面盒子的长和宽都要严格大于上面的。问最多能堆多少个盒子#xff1f; 解法1#xff1a;O(n^2)的动态规划解决。其实是最长递增子序列问题#xff0c;所以也可以用O(n * log(n))的优化算法。 代码… 2014-03-21 22:05 题目给你N个盒子堆成一座塔要求下面盒子的长和宽都要严格大于上面的。问最多能堆多少个盒子 解法1O(n^2)的动态规划解决。其实是最长递增子序列问题所以也可以用O(n * log(n))的优化算法。 代码 // 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()
{vectorBox v;vectorint 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用二分查找优化后的代码其中使用了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 algorithm4 #include cstdio5 #include vector6 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 vectorBox v;
25 vectorint dp;
26 vectorint::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 } 转载于:https://www.cnblogs.com/zhuli19901106/p/3616836.html
