题解

68 条题解

  • 3
    @ 2018-09-05 14:50:53
    //好题~
    //首先为了方便处理,把四个角上的点加入,再按横坐标进行排序
    //根据贪心的原理,最大子矩形的四边要么贴着边界,要么贴着某些点。这样
    //的话,当左边界确定后,完全可以从左到右遍历,每次更新上下边界和答案
    //
    //但这样的话会有遗漏的点,需要再从右向左反着再找一次,还有就是要按纵
    //坐标排序,直接更新两端顶着左右边界情况
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct node{
        int x,y;
    }q[5010];
    int cmp(const node&x,const node&y)
    {
        if(x.x!=y.x)
         return x.x<y.x;
        return x.y<y.y;
    }
    int cmp2(const node&x,const node&y)
    {
        return x.y<y.y;
    }
    
    int main()
    {
        int n,i,j,l,w,up,down,maxn=0;
        cin>>l>>w>>n;
        for(i=1;i<=n;i++)
         cin>>q[i].x>>q[i].y;
        q[n+1].x=l;
        q[n+1].y=w;
        q[n+2].x=l;
        q[n+2].y=0;
        q[n+3].x=0;
        q[n+3].y=w;
        q[n+4].x=0;
        q[n+4].y=0;
        n+=4;
        sort(q+1,q+n+1,cmp);
        for(i=1;i<=n;i++)
        {
            up=w;
            down=0;
            for(j=i+1;j<=n;j++)
            {
                maxn=max(maxn,(q[j].x-q[i].x)*(up-down));
                if(q[j].y==q[i].y)
                 break;
                if(q[j].y>q[i].y)
                 up=min(up,q[j].y);
                if(q[j].y<q[i].y)
                 down=max(down,q[j].y);
            }
        }
        for(i=n;i>0;i--)
        {
            up=w;
            down=0;
            for(j=i-1;j>0;j--)
            {
                maxn=max(maxn,(q[i].x-q[j].x)*(up-down));
                if(q[j].y==q[i].y)
                 break;
                if(q[j].y>q[i].y)
                 up=min(up,q[j].y);
                if(q[j].y<q[i].y)
                 down=max(down,q[j].y);
            }
        }
        sort(q+1,q+n+1,cmp2);
        for(i=2;i<=n;i++)
         maxn=max(maxn,(q[i].y-q[i-1].y)*l);
        cout<<maxn;
        return 0;
    }
    
  • 3
    @ 2017-09-11 22:59:37

    极大化思想......

    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    const int maxn=5005;
    
    int ans;
    int l,w,n;
    struct node{int x,y;}e[maxn];
    inline bool cp1(node a,node b){return a.x<b.x;}
    inline bool cp2(node a,node b){return a.y<b.y;}
    
    int main()
    {
        scanf("%d%d%d",&l,&w,&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&e[i].x,&e[i].y);
        e[++n].x=0,e[n].y=0;
        e[++n].x=0,e[n].y=w;
        e[++n].x=l,e[n].y=0;
        e[++n].x=l,e[n].y=w;
        sort(e+1,e+n+1,cp1);
        for(int i=1;i<n;i++)
        {
            int u=w,d=0;
            for(int j=i+1;j<=n;j++)
            {
                if(e[j].y>=d && e[j].y<=u)
                {
                    ans=max(ans,(e[j].x-e[i].x)*(u-d));
                    if(e[j].y>e[i].y) u=e[j].y;
                    else d=e[j].y;
                }
                if(u==d) break;
            }
        }
        sort(e+1,e+n+1,cp2);
        for(int i=1;i<n;i++)
        {
            int u=0,d=l;
            for(int j=i+1;j<=n;j++)
            {
                if(e[j].x>=u && e[j].x<=d)
                {
                    ans=max(ans,(e[j].y-e[i].y)*(d-u));
                    if(e[j].x>e[i].x) d=e[j].x;
                    else u=e[j].x;              
                }
                if(u==d) break;
            }
        }
        printf("%d",ans);
        return 0;
    }
    
  • 2
    @ 2013-06-30 17:59:20

    论文中2中特殊情况的解决方法:
    当左边界为0时,无须判断Y坐标大小,直接分成上部分和下部门继续计算,我用了递归。。
    var
    i,j,k,m,n,a1,a2,l,w,b1,b2,ans:Longint;
    x,y:array[0..15001]of longint;
    procedure go(k,u,d,l:Longint);
    var
    r:longint;
    begin
    if k>n then exit;
    r:=x[k];
    if (r=l) then begin go(k+1,u,d,l);exit;end;
    if (r-l)*(u-d)>ans then ans:=(r-l)*(u-d);
    if (u<=y[k])or(d>=y[k]) then begin go(k+1,u,d,l);exit;end;
    ×× if (y[k]>y[i])or(l=0) then go(k+1,y[k],d,l);××
    ××if (y[k]<y[i])or(l=0) then go(k+1,u,y[k],l);××

    end;
    procedure ins(a,b:Longint);
    begin
    inc(n);
    x[n]:=a;
    y[n]:=b;
    end;
    procedure first;
    begin
    ins(0,0);
    ins(0,w);
    ins(l,0);
    ins(l,w);
    end;
    begin
    read(l,w,n);
    for i:=1 to n do
    read(x[i],y[i]);
    first;
    for i:=1 to n do
    for j:=i+1 to n do
    if (x[i]>x[j])or((x[i]=x[j])and(y[i]<y[j])) then
    begin
    k:=x[i];x[i]:=x[j];x[j]:=k;
    k:=y[i];y[i]:=y[j];y[j]:=k;
    end;
    ans:=0;
    for i:=1 to n do
    go(i+1,w,0,x[i]);
    writeln(ans);
    end.

  • 1
    @ 2020-04-08 20:36:33

    我来简单的说一下:

    先枚举极大子矩形的左边界,然后从左到右依次扫描每一个障碍点,并不断修改可行的上下边界,从而枚举出所有以这个定点为左边界的极大子矩形。考虑如图2中的三个点,现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点,同时记录下当前的可行的上下边界。


    开始时令当前的上下边界分别为整个矩形的上下边界。然后开始扫描。第一次遇到2号点,以2号点作为右边界,结合当前的上下边界,就得到一个极大子矩形(如图3)。


    同时,由于所求矩形不能包含2号点,且2号点在1号点的下方,所以需要修改当前的下边界,即以2号点的纵坐标作为新的下边界。第二次遇到3号点,这时以3号点的横坐标作为右边界又可以得到一个满足性质1的矩形(如图4)。

    类似的,需要相应地修改上边界。以此类推,如果这个点是在当前点(确定左边界的点)上方,则修改上边界;如果在下方,则修改下边界;如果处在同一行,则可中止搜索(因为后面的矩形面积都是0了)。由于已经在障碍点集合中增加了整个矩形右上角和右下角的两个点,所以不会遗漏右边界与整个矩形的右边重合的极大子矩形(如图5)。


    需要注意的是,如果扫描到的点不在当前的上下边界内,那么就不需要对这个点进行处理。

    这样做是否将所有的极大子矩形都枚举过了呢?

    可以发现,这样做只考虑到了左边界覆盖一个点的矩形,因此我们还需要枚举左边界与整个矩形的左边界重合的情况。这还可以分为两类情况。一种是左边界与整个举行的左边界重合,而右边界覆盖了一个障碍点的情况,对于这种情况,可以用类似的方法从右到左扫描每一个点作为右边界的情况。这就是上面第一个数据楼下二位错在哪里。
    另一种是左右边界均与整个矩形的左右边界重合的情况,对于这类情况我们可以在预处理中完成:先将所有点按纵坐标排序,然后可以得到以相邻两个点的纵坐标为上下边界,左右边界与整个矩形的左右边界重合的矩形,显然这样的矩形也是极大子矩形,因此也需要被枚举到。

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define re register
    #define REP(i,a,b) for (re int i=(a);i<=(b);i++)
    #define DREP(i,a,b) for (re int i=(a);i>=(b);i--)
    using namespace std;
    const int N=5e3+7;
    struct Cow{
        int x,y;
        inline bool operator < (const Cow &rhs) const {
            if (x!=rhs.x)return x<rhs.x;
            return y<rhs.y;
        }
    }a[N];
    int L,W,n;
    inline bool cmp(Cow a,Cow b){
        return a.y<b.y;
    }
    inline int read(){
        re int x=0,f=1;char ch=getchar();
        while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
        while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return x*f;
    }
    int main(){
        L=read(),W=read(),n=read();
        REP(i,1,n)a[i].x=read(),a[i].y=read();
        a[++n].x=0;a[n].y=0;
        a[++n].x=L;a[n].y=0;
        a[++n].x=0;a[n].y=W;
        a[++n].x=L;a[n].y=W;
        sort(a+1,a+n+1);
        int res=0;
        REP(i,1,n){
            re int h=W,l=0,v=L-a[i].x;
            REP(j,i+1,n)if (a[j].y<=h && a[j].y>=l){
                if (v*(h-l)<=res)break;
                res=max(res,(a[j].x-a[i].x)*(h-l));
                if (a[j].y==a[i].y)break;
                if (a[j].y>a[i].y)h=min(h,a[j].y);
                else l=max(l,a[j].y);
            }
            h=W,l=0,v=a[i].x;//王知昆dalao在此处仍将v设为l-a[i].x,这显然不对,可以自己想一想。
            DREP(j,i-1,1)
                if (a[j].y<=h && a[j].y>=l){
                if (v*(h-l)<=res)break;
                res=max(res,(a[i].x-a[j].x)*(h-l));
                if (a[i].y==a[j].y)break;
                if (a[j].y>a[i].y)h=min(h,a[j].y);
                else l=max(l,a[j].y);
            }
        }
        sort(a+1,a+n+1,cmp);
        REP(i,1,n-1)res=max(res,(a[i+1].y-a[i].y)*L);
        printf("%d",res);
        return 0;
    }
    
  • 1
    @ 2020-03-03 15:46:59
    //是测试数据有误吗?
    //我按照 猫粮寸断的思路来写, 左右只遍历一遍, 也能AC
    #include <iostream>             //最大子矩形,    (极大化思想)
    #include <algorithm>
    using namespace std;
    const int Maxn = 5010;
    
    int L, W, n;
    int maxS = 0;
    
    struct node {
        int i, j;
    }Poi[Maxn];
    
    bool cp_i(node a, node b) { return a.i < b.i; }
    
    bool cp_j(node a, node b) { return a.j < b.j; }
    
    void Scanf_Poi()
    {
        for (int i = 0; i < n; i++)
            cin >> Poi[i].i >> Poi[i].j;
        Poi[n].i = 0; Poi[n].j = 0;             //插入4个角
        Poi[n + 1].i = 0; Poi[n + 1].j = W;
        Poi[n + 2].i = L; Poi[n + 2].j = 0;
        Poi[n + 3].i = L; Poi[n + 3].j = W;
        n += 4;
    }
    
    void Rectangle()
    {
        int up, down;
        sort(Poi, Poi + n, cp_i);
        for (int i = 0; i < n - 1; i++)
        {
            up = W, down = 0;
            for (int j = i + 1; j < n; j++)
            {
                if (Poi[j].j >= down && Poi[j].j <= up)
                {
                    maxS = max(maxS, (up - down) * (Poi[j].i - Poi[i].i));
                    if (Poi[j].j < Poi[i].j)        //j点在i点下面, 更新下边届
                        down = Poi[j].j;
                    else                            //否则, 更新上边届
                        up = Poi[j].j;
                }
                if (up == down)
                    break;
            }
        }
        
        sort(Poi, Poi + n, cp_j);
        for (int i = 1; i < n; i++)
        {
            maxS = max(maxS, (Poi[i].j - Poi[i - 1].j) * L);
        }
    
    }
    
    int main()
    {
        cin >> L >> W >> n;
        Scanf_Poi();
        Rectangle();
        
        cout << maxS << endl;
    
        system("pause");
        return 0;
    }
    
    
  • 0
    @ 2017-04-08 18:00:42
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    static const int maxm=1e6+10;
    
    struct point{
        int x,y;
    }pt[maxm];
    
    int n,l,w,ans=-1;
    
    bool cmp1(const point& A,const point &B){
        return A.x==B.x?A.y<B.y:A.x<B.x;
    }
    
    bool cmp2(const point &A,const point &B){
        return A.y==B.y?A.x<B.x:A.y<B.y;
    }
    
    int main(){
        scanf("%d%d%d",&l,&w,&n);
        if(!n)return printf("%d\n",l*w),0;
        for(int i=1;i<=n;i++)scanf("%d%d",&pt[i].x,&pt[i].y);
    
        sort(pt+1,pt+n+1,cmp1);
        
        for(int i=1;i<=n;i++){
            int u=w;int d=0;
            for(int j=i+1;j<=n;j++){
            ans=max(ans,(u-d)*(pt[j].x-pt[i].x));
            if(pt[j].y>=pt[i].y)u=min(u,pt[j].y);
            if(pt[j].y<=pt[i].y)d=max(d,pt[j].y);
            }
            ans=max(ans,(l-pt[i].x)*(u-d));
       }
    
        for(int i=n;i>=1;i--){
                int u=w;int d=0;
                for(int j=i-1;j>=1;j--){
                ans=max(ans,(u-d)*(pt[i].x-pt[j].x));
                if(pt[j].y>=pt[i].y)u=min(u,pt[j].y);
                if(pt[j].y<=pt[i].y)d=max(d,pt[j].y);
            }
            ans=max(ans,pt[i].x*(u-d));
        }
    
        sort(pt+1,pt+n+1,cmp2);
    
        for(int i=1;i<n;i++)
            ans=max(ans,l*(pt[i+1].y-pt[i].y));
        
        printf("%d\n",ans);
        
        return 0;
    }
    
  • 0
    @ 2016-04-15 10:40:12

    要特判没有产奶点的情况,不然会wa第一个点
    #include<cstdio>
    struct record
    {
    int x,y;
    };
    record p[5001];
    bool compare1(record a,record b)
    {
    return a.x<b.x;
    }
    bool compare2(record a,record b)
    {
    return a.y<b.y;
    }
    int ans=0,u,d,m,n,k;
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    if(!k)
    {printf("%d",m*n);return 0;}
    for(int i=1;i<=k;++i)
    scanf("%d%d",&p[i].x,&p[i].y);
    std::sort(p+1,p+k+1,compare1);
    for(int i=1;i<=k;++i)
    {
    u=m,d=0;
    for(int j=i+1;j<=k;++j)
    {
    ans=std::max(ans,(p[j].x-p[i].x)*(u-d));
    if(p[j].y==p[i].y)
    {u=d=p[i].y;break;}
    else
    if(p[j].y>p[i].y)
    u=std::min(u,p[j].y);
    else
    d=std::max(d,p[j].y);
    }
    ans=std::max(ans,(n-p[i].x)*(u-d));
    }
    for(int i=k;i;--i)
    {
    u=m,d=0;
    for(int j=i-1;j;--j)
    {
    ans=std::max(ans,(p[i].x-p[j].x)*(u-d));
    if(p[j].y==p[i].y)
    {u=d=p[i].y;break;}
    else
    if(p[j].y>p[i].y)
    u=std::min(u,p[j].y);
    else
    d=std::max(d,p[j].y);
    }
    ans=std::max(ans,p[i].x*(u-d));
    }
    std::sort(p+1,p+k+1,compare2);
    for(int i=1;i<k;++i)
    ans=std::max(ans,(p[i+1].y-p[i].y)*n);
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2013-12-16 19:02:34

    测试数据 #0: Accepted, time = 0 ms, mem = 480 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 472 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 468 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 476 KiB, score = 10
    测试数据 #4: Accepted, time = 93 ms, mem = 476 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 472 KiB, score = 10
    测试数据 #6: Accepted, time = 109 ms, mem = 480 KiB, score = 10
    测试数据 #7: Accepted, time = 156 ms, mem = 468 KiB, score = 10
    测试数据 #8: Accepted, time = 171 ms, mem = 472 KiB, score = 10
    测试数据 #9: Accepted, time = 62 ms, mem = 468 KiB, score = 10
    Accepted, time = 591 ms, mem = 480 KiB, score = 100
    最开始脑残了,上下边界的处理出现了问题,后来改正就AC了,或许因为我过多使用了封装的东西,导致稍稍慢了点儿吧
    具体的思想就是枚举左右边界,先确定一个左边界,枚举右边界,不断地修改上下边界,这样的话一定会得到一个最大的子矩形。
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn = 5050;
    struct node{
    int x, y;
    bool operator < (const node &rhs)const{
    return rhs.x < x;
    }
    };
    node s[maxn];
    int w, l, n;
    int main(){
    scanf("%d%d", &l, &w);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &s[i].x, &s[i].y);
    s[n++] = (node){0, 0}; s[n++] = (node){w, 0};
    s[n++] = (node){0, l}; s[n++] = (node){w, l};
    sort(s, s + n);
    int left, right, up, down;
    int ans = 0;
    for (int i = 0; i < n; i++){
    left = s[i].x; up = 0; down = l;
    for (int j = i + 1; j < n; j++){
    if (s[j].x == left) continue;
    right = s[j].x;
    int ss = abs((right - left) * (down - up));
    ans = max(ans, ss);
    if (s[j].y < down && s[j].y >= s[i].y){down = s[j].y;}
    if (s[j].y > up && s[j].y <= s[i].y){up = s[j].y;}
    if (up >= down) break;
    }
    }
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2013-10-27 10:10:55

    感谢 王知昆《浅谈用极大化思想解决最大子矩形问题》 给我的指导!

  • 0
    @ 2012-07-30 09:12:16

    极大化思想

    先排序

    把4个顶点加上 作为边界

    for(i=1;i

  • 0
    @ 2009-11-08 22:23:15

    最大子矩形问题..

    极大化思想

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 72ms

    ├ 测试数据 09:答案正确... 150ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:247ms

    题解:

    http://254117343.blog.163.com/

  • 0
    @ 2009-09-27 14:46:27

    s表示障碍点数量,定义极大子矩形表示上下左右边界上都有障碍点。

    O(s^2)做法:

    分三种情况,一种是左边界在边界上且右边界不在边界上的,一种是左边界右边界都在边界上的,一种左边界上有障碍点而右边界上没有的。

    对于第二种,预处理。

    对于第三种,枚举左边界上的点,枚举右边界,并维护以该点为左边界上的点的极大子矩形即可。

    对于第一种,类似第三种。

    O(nm)做法:

    定义u[i][j]表示从(i,j)往上最大能延伸的长度。l[i][j]表示以u[i][j]为宽

    ,以(i,j)为右下角,往左最大延伸长度。r[i][j]同l[i][j]。则l,r可以从(i-

    1,j)推得。接下来枚举(i,j),求max(u[i][j]*(l[i][j]+r[i][j]))即可

    即使障碍点多,也可以离散以后用NM做法。

  • 0
    @ 2009-09-20 21:46:56

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    交了五六次后……过了……

    学了极大化……秒杀……

    晒晒……

    =========================puppy的分割线=========================

    program v1055;

    type rec=record

    x,y:longint;

    end;

    var a:array[0..5005] of rec;

    i,j,l,w,k,u,d,s,n,temp,r:longint;

    procedure qsort(s,e:longint);

    var t:rec;

    x,i,j:longint;

    begin

    i:=s; j:=e;

    x:=a[random(e-s)+s].x;

    repeat

    while a[i].xx do dec(j);

    if ij;

    if is then qsort(s,j);

    end;

    begin

    readln(l,w);

    readln(n);

    for i:=1 to n do

    readln(a[i].x,a[i].y);

    i:=n;

    a[n+1].x:=0; a[n+1].y:=0;

    a[n+2].x:=l; a[n+2].y:=0;

    a[n+3].x:=0; a[n+3].y:=w;

    a[n+4].x:=l; a[n+4].y:=w;

    randomize;

    qsort(1,n+4);

    s:=0;

    for i:=1 to n+3 do

    begin

    u:=0; d:=w;

    for j:=i+1 to n+4 do

    begin

    if (a[j].x=a[i].x)or(a[j].y>d)or(a[j].ys then s:=temp;

    if (a[j].y=a[i].y) then d:=a[j].y;

    if (a[j].y>u)and(a[j].y=d then break;

    end;

    end;

    writeln(s);

    end.

  • 0
    @ 2009-10-03 12:21:32

    极大化思想。。不过我的编程能力不时很强。。没有秒杀(尽管来鄙视我吧)

    这里有论文的图片版:

    http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/a441612a79790cf0e6cd4087.html

  • 0
    @ 2009-09-07 13:20:19

    极大化思想 强!!!

  • 0
    @ 2009-08-28 14:40:22

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    orz WZK

  • 0
    @ 2009-08-25 09:37:55

    Accepted 有效得分:100 有效耗时:146ms

    一开始想到一个s^3的算法没敢写,不知道会不会超......

    看完WC2003WZK的论文后---|1次AC(好爽)!

    强大的极大化矩阵.s^2

  • 0
    @ 2009-08-16 14:40:53

    郁闷,小错误不断,快排的时候注意别调用错程序.....

  • 0
    @ 2009-08-11 12:51:55

    这题障碍点才5000个,当然选(s^2)啦。(N*M)反倒更大。

  • 0
    @ 2009-08-09 14:37:55

    样例?

信息

ID
1055
难度
6
分类
动态规划 点击显示
标签
递交数
2095
已通过
644
通过率
31%
被复制
8
上传者