m*t
2 楼
http://community.topcoder.com/stat?c=problem_statement&pm=12928
Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
through N-1. You are given int[]s X and Y with N elements each. For each i,
the sides of rectangle i have lengths X[i] and Y[i].
Snake Snuke will choose some of his rectangles and place them onto a table,
one rectangle at a time, in any order he likes. Each rectangle (except for
the first one) must overlap the immediately previous one, so at the end
Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
once placed, the sides of each rectangle must be parallel to the sides of
the table. (I.e., he may only swap the width and height of some rectangles
he places.) After placing all the rectangles, Snuke computes the area that
is covered by all N rectangles. (Formally, the area of their intersection.)
You are also given an int limit. The area computed by Snuke must be greater
than or equal to limit.
Return the largest positive R such that Snuke can select some R of his
rectangles and place them in such a way that the area of their intersection
is at least limit. If there is no such R, return -1 instead.
我觉得这个算是一个 combinatorial optimization 和 computational geometry 结合
的问题。 问题现在是，能不能用 knapsack 类似的 DP 方法做到 polynomial time 解
法？
Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
through N-1. You are given int[]s X and Y with N elements each. For each i,
the sides of rectangle i have lengths X[i] and Y[i].
Snake Snuke will choose some of his rectangles and place them onto a table,
one rectangle at a time, in any order he likes. Each rectangle (except for
the first one) must overlap the immediately previous one, so at the end
Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
once placed, the sides of each rectangle must be parallel to the sides of
the table. (I.e., he may only swap the width and height of some rectangles
he places.) After placing all the rectangles, Snuke computes the area that
is covered by all N rectangles. (Formally, the area of their intersection.)
You are also given an int limit. The area computed by Snuke must be greater
than or equal to limit.
Return the largest positive R such that Snuke can select some R of his
rectangles and place them in such a way that the area of their intersection
is at least limit. If there is no such R, return -1 instead.
我觉得这个算是一个 combinatorial optimization 和 computational geometry 结合
的问题。 问题现在是，能不能用 knapsack 类似的 DP 方法做到 polynomial time 解
法？
Y*e
3 楼
开一千年 落一千年 花叶永不相见
h*e
4 楼
是呀，我每次看到病人的message就很紧张。
c*n
5 楼
这题可以O(n3)
遍历所有pair of rectangle, 对于每个pair 可以得到两个(因为可以旋转)相交区域的
lower bound (x' , y'). 这时res = 2
如果x' * y' >= limit
然后对剩下的rectangle 如果其长和宽都大于对应(x', y') 就res++
最后取最大的res
如果所有lower bound < limit, 返回－1
int getNum(int l1, int l2, int w1, int w2, vector& X, vector&
Y, int limit, int i, int j) {
int l = l1 < l2? l1:l2;
int w = w1 < w2? w1:w2;
if(l * w >= limit) {
int res = 2;
for(int k = 0; k < X.size(); k++) {
if(k != i && k != j) {
int kl = X[k];
int kw = Y[k];
if((kl >= l && kw >= w) || (kl >= w && kw >= l)) {
res++;
}
}
}
return res;
} else {
return 1;
}
}
int getmax(vector X, vector Y, int limit) {
int largest = 0;
for(int i = 0; i < X.size(); i++) {
int area = X[i] * Y[i];
if(area > largest) {
largest = area;
}
}
if(largest < limit) {
return -1;
}
int res = 1;
for(int i = 0; i < X.size(); i++) {
int l1 = X[i];
int w1 = Y[i];
for(int j = i + 1; j < X.size(); j++) {
int l2 = X[j];
int w2 = Y[j];
int tmp = getNum(l1, l2, w1, w2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
tmp = getNum(l1, w2, w1, l2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
}
}
return res;
}
遍历所有pair of rectangle, 对于每个pair 可以得到两个(因为可以旋转)相交区域的
lower bound (x' , y'). 这时res = 2
如果x' * y' >= limit
然后对剩下的rectangle 如果其长和宽都大于对应(x', y') 就res++
最后取最大的res
如果所有lower bound < limit, 返回－1
int getNum(int l1, int l2, int w1, int w2, vector
Y, int limit, int i, int j) {
int l = l1 < l2? l1:l2;
int w = w1 < w2? w1:w2;
if(l * w >= limit) {
int res = 2;
for(int k = 0; k < X.size(); k++) {
if(k != i && k != j) {
int kl = X[k];
int kw = Y[k];
if((kl >= l && kw >= w) || (kl >= w && kw >= l)) {
res++;
}
}
}
return res;
} else {
return 1;
}
}
int getmax(vector
int largest = 0;
for(int i = 0; i < X.size(); i++) {
int area = X[i] * Y[i];
if(area > largest) {
largest = area;
}
}
if(largest < limit) {
return -1;
}
int res = 1;
for(int i = 0; i < X.size(); i++) {
int l1 = X[i];
int w1 = Y[i];
for(int j = i + 1; j < X.size(); j++) {
int l2 = X[j];
int w2 = Y[j];
int tmp = getNum(l1, l2, w1, w2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
tmp = getNum(l1, w2, w1, l2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
}
}
return res;
}
s*s
6 楼
刷点小儿科的。这么深奥理解不了
g*i
7 楼
呵呵，啥时候到病人看到你msg就紧张就好了。
【在 h*e 的大作中提到】
: 是呀，我每次看到病人的message就很紧张。
【在 h*e 的大作中提到】
: 是呀，我每次看到病人的message就很紧张。
r*7
8 楼
可是knapsack是NP问题啊。。。哪儿有多项式解法
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
Y*e
9 楼
你刷，我跟
好像以前那样
【在 s****s 的大作中提到】
: 刷点小儿科的。这么深奥理解不了
好像以前那样
【在 s****s 的大作中提到】
: 刷点小儿科的。这么深奥理解不了
r*7
10 楼
刚好刷到这题。。。
greedy就可以了
typedef map > RectType;
int PilingRectsDiv2::getmax(vector X, vector Y, int limit) {
size_t sz = X.size();
RectType rects;
int result = -1;
for (size_t i = 0; i < sz; i ++) {
int h = X[i] < Y[i] ? X[i] : Y[i];
int w = X[i] < Y[i] ? Y[i] : X[i];
if (h * w < limit) {
continue;
}
if (rects.find(h) == rects.end()) {
rects[h] = vector(1, w);
} else {
rects[h].push_back(w);
}
}
RectType::iterator it;
for (it = rects.begin(); it != rects.end(); it ++) {
sort(it->second.begin(), it->second.end());
}
for (it = rects.begin(); it != rects.end(); it ++) {
int currH = it->first;
RectType::iterator nit;
int oneResult = 0;
for (nit = it; nit != rects.end(); nit ++) {
// can use binary search to opt
for (size_t i = 0; i < nit->second.size(); i ++) {
if (currH * nit->second[i] >= limit) {
oneResult += nit->second.size() - i;
break;
}
}
}
result = max(result, oneResult);
}
return result;
}
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
greedy就可以了
typedef map
int PilingRectsDiv2::getmax(vector
size_t sz = X.size();
RectType rects;
int result = -1;
for (size_t i = 0; i < sz; i ++) {
int h = X[i] < Y[i] ? X[i] : Y[i];
int w = X[i] < Y[i] ? Y[i] : X[i];
if (h * w < limit) {
continue;
}
if (rects.find(h) == rects.end()) {
rects[h] = vector
} else {
rects[h].push_back(w);
}
}
RectType::iterator it;
for (it = rects.begin(); it != rects.end(); it ++) {
sort(it->second.begin(), it->second.end());
}
for (it = rects.begin(); it != rects.end(); it ++) {
int currH = it->first;
RectType::iterator nit;
int oneResult = 0;
for (nit = it; nit != rects.end(); nit ++) {
// can use binary search to opt
for (size_t i = 0; i < nit->second.size(); i ++) {
if (currH * nit->second[i] >= limit) {
oneResult += nit->second.size() - i;
break;
}
}
}
result = max(result, oneResult);
}
return result;
}
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
s*s
11 楼
。。。
奔奔最近怎样？
【在 Y****e 的大作中提到】
: 你刷，我跟
: 好像以前那样
奔奔最近怎样？
【在 Y****e 的大作中提到】
: 你刷，我跟
: 好像以前那样
Y*e
12 楼
写不出一个字．憋着
【在 s****s 的大作中提到】
: 。。。
: 奔奔最近怎样？
【在 s****s 的大作中提到】
: 。。。
: 奔奔最近怎样？
相关阅读
征译文转移阵地，不求最好，只求最合适。[女征男]说找有缘人是不是太土，不够酷，可这事，真的还是得靠缘分！李天乐37岁结婚，丈夫要离婚而绝望杀人纽约华裔女子与同居男友分手 不还钻戒被指控 (转载)29岁的上海女码农 vs 31岁的硅谷女码农女屌丝一枚Re: 被骗了， 谁整天说湾区男多女少？ (转载)搬运的要注意了，看看这些北漂/上海飘荡的女都是什么人。 (转载)【男征女】纽约豪放男找女友（附照片）san jose女征男代人发帖【女征男】寻找另一半发歌，祝有情人终成眷属。满版面的女征男我来具体说一说为什么选我是个不错的选择是不是这样的女人大有人在男人娶女人：性格温柔>身材脸蛋>挣钱多 (转载)【女征男】 附照片 在回复里 就是一个普通女生而已铁打的营盘流水的兵啊。。求搬运