68 条题解
-
0
tobright LV 10 @ 2008-08-02 13:19:13
先对数据进行排序，快排就可以了（地球人都知道要排序）。
然后讲讲搜索的放法。
先从小娶一个点，此时你已经控制了半个矩形，画一画
#---|---|---|---|---|---| (# 表示该点)，
|
|
|
|
|
|
|
|
然后你就寻找另一个点（其实我先前以为是dp，但是没有头绪，看了题解才知道大牛们用搜索做的）
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 56ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：112ms -
-1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct point
{
int x,y;
}e[50010];
int l,w,k,ans;
int cmp(const point&a,const point&b)
{
if(a.x<b.x)
return 1;
return 0;
}
int main()
{
scanf("%d%d",&l,&w);
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
}
e[++k].x=0;e[k].y=0;
e[++k].x=0;e[k].y=w;
e[++k].x=l;e[k].y=0;
e[++k].x=l;e[k].y=w;
sort(e+1,e+k+1,cmp);
for(int i=1;i<=k;i++)
{
int x=0;
int y=w;
for(int j=i+1;j<=k;j++)
{
if(e[i].x==e[j].x||e[j].y>y||e[j].y<x)
continue;
ans=max(ans,(e[j].x-e[i].x)*(y-x));
if(e[j].y>x&&e[j].y<=e[i].y)
x=e[j].y;
if(e[j].y<y&&e[j].y>=e[i].y)
y=e[j].y;
if(x>=y)break;
}
}
printf("%d",ans);
return 0;
} -
-1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct point
{
int x,y;
}e[50010];
int l,w,k,ans;
int cmp(const point&a,const point&b)
{
if(a.x<b.x)
return 1;
return 0;
}
int main()
{
scanf("%d%d",&l,&w);
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
}
e[++k].x=0;e[k].y=0;
e[++k].x=0;e[k].y=w;
e[++k].x=l;e[k].y=0;
e[++k].x=l;e[k].y=w;
sort(e+1,e+k+1,cmp);
for(int i=1;i<=k;i++)
{
int x=0;
int y=w;
for(int j=i+1;j<=k;j++)
{
if(e[i].x==e[j].x||e[j].y>y||e[j].y<x)
continue;
ans=max(ans,(e[j].x-e[i].x)*(y-x));
if(e[j].y>x&&e[j].y<=e[i].y)
x=e[j].y;
if(e[j].y<y&&e[j].y>=e[i].y)
y=e[j].y;
if(x>=y)break;
}
}
printf("%d",ans);
return 0;
} -
-1
feng_lingsong LV 9 @ 2016-08-30 10:14:25
数据太弱了
参考了论文《浅谈用极大化思想解决最大子矩形问题》
我提交以下代码的时候，本来是想看看数据出的怎么样，结果就阴差阳错的直接AC了
以下代码有几种情况不能解决，一种是包含左右边界一部分的情况，一种是有两点的纵坐标相同的情况，但也懒得加了.....
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define dwn(i, x, y) for (int i = x; i >= y; --i)using namespace std;
struct node {
int x, y;
bool operator < (const node &xx) const {
return x < xx.x;
}
} point[5005];int l, w, n;
int main(int argc, const char *argv[]) {
scanf("%d%d%d", &l, &w, &n);
rep(i, 1, n) scanf("%d %d", &point[i].x, &point[i].y);
point[++n] = (node){0, 0};
point[++n] = (node){0, w};
point[++n] = (node){l, 0};
point[++n] = (node){l, w};
sort(point + 1, point + n + 1);
int up, down, smax = 0;
rep(i, 1, n) {
up = w, down = 0;
int s;
rep(j, i + 1, n) {
s = (point[j].x - point[i].x) * (up - down);
if (s > smax) smax = s;
if (point[j].y > point[i].y && point[j].y < up) up = point[j].y;
if (point[j].y < point[i].y && point[j].y > down) down = point[j].y;
if (point[j].y == point[i].y) {
smax = max(smax, (point[j].x - point[i].x) * (up - down));
break;
}
}
}
dwn(i, n, 1) {
up = w, down = 0;
int s;
dwn(j, i - 1, 1) {
s = (point[i].x - point[j].x) * (up - down);
if (s > smax) smax = s;
if (point[j].y > point[i].y && point[j].y < up) up = point[j].y;
if (point[j].y < point[i].y && point[j].y > down) down = point[j].y;
if (point[j].y == point[i].y) {
smax = max(smax, (point[i].x - point[j].x) * (up - down));
break;
}
}
}
rep(i, 1, n)
printf("%d\n", smax);
return 0;
} -
-1
caesar_199 LV 9 @ 2016-05-07 18:38:11
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int ans; int u, v; int l, w; int n; int up; int dow; int tems; int x[5100]; int y[5100]; int r[5100]; int r2[5100]; bool cmp (int a, int b) { return x[a] < x[b]; } bool cmp1 (int a, int b) { return y[a] > y[b]; } int main () { //freopen ("in.txt", "r", stdin); cin >> l >> w; cin >> n; if (n == 0) { cout << w * l; return 0; } for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; r[i] = r2[i] = i; } sort (r, r + n, cmp); for (int i = 0; i < n; i++) { u = r[i]; up = w; dow = 0; for (int j = i + 1; j < n; j++) { v = r[j]; if (y[v] <= up && y[v] >= dow) { tems = (up - dow) * (x[v] - x[u]); ans = max(tems, ans); if (y[v] > y[u]) up = y[v]; else if (y[v] < y[u]) dow = y[v]; else if (y[v] == y[u]) { up = dow; break;} } } if (up != dow) { tems = (up - dow) * (l - x[u]); ans = max (ans, tems); } } for (int i = n - 1; i >= 0; i--) { u = r[i]; up = w; dow = 0; for (int j = i - 1; j >= 0; j--) { v = r[j]; if (y[v] <= up && y[v] >= dow) { if (y[v] > y[u]) up = y[v]; else if (y[v] < y[u]) dow = y[v]; else if (y[v] == y[u]) { up = dow; break;} } } if (up != dow) { tems = (up - dow) * x[u]; ans = max (ans, tems); } } sort (r2, r2 + n, cmp1); tems = l * (w - y[r2[0]]); ans = max (ans, tems); tems = l * y[r2[n-1]]; ans = max (ans, tems); for (int i = 0; i < n - 1; i++) { u = r2[i]; v = r2[i + 1]; tems = l * (y[u] - y[v]); ans = max (tems, ans); } cout << ans; return 0; } -
-1
正在加载...99% LV 8 @ 2016-04-21 21:45:46
const
maxn = 5100;
var
n : integer;
x, y : array[0 .. maxn] of integer;
w, h : integer;
result : longint;
procedure getinfo;
var
i : integer;
begin
readln(w, h);
readln(n);
for i := 1 to n do readln(x[i], y[i]);
end;
procedure print;
begin
writeln(result);
end;
procedure sort;
var
i : integer;
procedure swap(var x, y : integer);
var
t : integer;
begin
t := x; x := y; y := t;
end;
procedure sift(s, t : integer);
var
i, j : integer;
begin
i := s; j := i + i;
while j <= t do begin
if (j < t) and (y[j + 1] > y[j]) then inc(j);
if y[i] >= y[j] then break else begin
swap(y[i], y[j]); swap(x[i], x[j]); i := j; j := i + i;
end;
end;
end;
begin
for i := n shr 1 downto 1 do sift(i, n);
for i := n downto 2 do begin
swap(x[1], x[i]); swap(y[1], y[i]);
sift(1, i - 1)
end;
end;
procedure initresult;
var
maxw : longint;
p, i, l, t : integer;
d : array[0 .. maxn] of integer;
begin
fillchar(d, sizeof(d), 0);
result := 0;
l := 2; d[1] := 0; d[2] := w; maxw := w;
for t := 1 to n do begin
if maxw * y[t] > result then result := maxw * y[t];
p := 1; while d[p] < x[t] do inc(p);
for i := l + 1 downto p + 1 do d[i] := d[i - 1];
d[p] := x[t]; inc(l);
maxw := 0;
for i := l downto 2 do if d[i] - d[i - 1] > maxw then maxw := d[i] - d[i - 1];
end;
if maxw * h > result then result := maxw * h;
end;
procedure main;
var
l, r : longint;
s, i, j : integer;
begin
for i := 1 to n do begin
l := 0; r := w; s := i + 1;
while (s <= n) and (y[s] = y[i]) do inc(s);
for j := s to n do begin
if (r - l) * (y[j] - y[i]) > result then result := (r - l) * (y[j] - y[i]);
if (x[j] <= x[i]) and (x[j] > l) then l := x[j];
if (x[j] >= x[i]) and (x[j] < r) then r := x[j];
end;
if (r - l) * (h - y[i]) > result then result := (r - l) * (h - y[i]);
end;
end;
begin
getinfo;
sort;
initresult;
main;
print;
end. -
-1
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 864 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 852 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 856 KiB, score = 10
测试数据 #7: WrongAnswer, time = 109 ms, mem = 856 KiB, score = 0
测试数据 #8: Accepted, time = 109 ms, mem = 856 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 852 KiB, score = 10
WrongAnswer, time = 404 ms, mem = 864 KiB, score = 90
第七个WA…… -
-1
我只处理了左边界或右边界重合的情况
没有判断左右边界同时重合的情况，还是A了....可能是数据太弱
（同学习了王知昆的《浅谈用极大化思想解决最大子矩形问题》...）具体的，如何处理边界情况，可见蒟蒻的题解 http://www.cnblogs.com/polebug/p/4005487.html
-
polebug @ 2014-10-03 23:52:29
但是加了一个n=0的特判
-
-
-1
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 56ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：130ms -
-1
lonelycorn LV 3 @ 2007-11-12 14:29:17
so easy~就是时间有点长，后面几个点都200+ms
不过自己写的就差不多吧~
参见2002WC的王知昆的论文~ -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 41ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 416ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 181ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：844ms还不差，贴出来
tobright
LV 10
@ 2008-08-02 13:19:13
信息
- ID
- 1055
- 难度
- 5
- 分类
- 动态规划 点击显示
- 标签
- 递交数
- 2106
- 已通过
- 653
- 通过率
- 31%
- 被复制
- 10
- 上传者
-
xiaomengxian
