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 楼
刷点小儿科的。这么深奥理解不了
r*7
8 楼
可是knapsack是NP问题啊。。。哪儿有多项式解法
0
,
,
【在 m*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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
相关阅读
解决办法: 多见面,少设限37岁中年失婚女人就只能嫁50岁的男人?Get over it. We are all commodities in dating marketcoask 封 DQSL 在 Piebridge 版这里能不能征去公司圣诞party的我写了个小程序,专们用来对付你们这些闪奔的!!!!大龄男找不到老婆 Vs 大龄女找不到男人听说劝退劝退,不要征婚啦少点抱怨北美高智商女情商有待提高“別jjyy的,还是男人不是!”??为什么女人的要求那么多? (转载)美国WSN那宿命般的未来的老婆[合集] 剩女劣根性中国帅哥求婚非洲女友“黑白配”Dallas征女替39岁国内离异的同学哥哥求搬运自己从不过生日,也不记得其他亲友等人的生日要像防贼一样防着男人