题解

59 条题解

  • 0
    @ 2018-09-22 20:53:38

    DFS+分支界限法剪枝
    虽然是很套路的题,但写了好久好久……实在是想不到“各个矩形必须完全分开”的简单实现方式,所以代码的内容越来越多……

    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <stack>
    #include <algorithm>
    #define MAX 100000000
    #define NLIMIT 50
    #define KLIMIT 4
    using namespace std;
    
    int n,k,ans=MAX;
    struct node
    {
        int area;
        int num;//即将要选的点
        int re[KLIMIT][NLIMIT-KLIMIT+1];//点的顺序号
        int p[KLIMIT];//点的数目
        int maxx[KLIMIT];
        int minx[KLIMIT];
        int maxy[KLIMIT];
        int miny[KLIMIT];
        node():area(0),num(0)
        {
            for(int i=0;i<KLIMIT;i++)
            {
                p[i]=0;
                minx[i]=MAX;
                miny[i]=MAX;
            }
            memset(re,-1,sizeof(re));
            memset(maxx,-1,sizeof(maxx));
            memset(maxy,-1,sizeof(maxy));
        }
    };
    stack<node> st;
    
    void DFS(int x[],int y[])
    {
        node t;
        st.push(t);
        while(st.empty()==false)
        {
            t=st.top();
            st.pop();
            if(t.area>ans)//优化剪枝
                continue;
            if(t.num==n)
            {
                int flag=1;
                for(int i=0;i<k;i++)
                    if(t.p[i]==0)
                    {
                        flag=0;
                        break;
                    }
                if(flag==0)
                    continue;
                else
                    ans=min(ans,t.area);
            }
            else
                for(int i=0;i<k;i++)
                {
                    node aot=t;
                    aot.re[i][t.p[i]]=t.num;
                    aot.p[i]=t.p[i]+1;
                    aot.num=t.num+1;
                    aot.maxx[i]=max(aot.maxx[i],x[t.num]);
                    aot.maxy[i]=max(aot.maxy[i],y[t.num]);
                    aot.minx[i]=min(aot.minx[i],x[t.num]);
                    aot.miny[i]=min(aot.miny[i],y[t.num]);
                    int flag=1;
                    for(int j=0;j<k-1;j++)
                        if(aot.p[j]!=0)
                        {
                            for(int q=j+1;q<k;q++)
                                if(aot.p[q]!=0)
                                {
                                    if(aot.maxx[j]>=aot.minx[q]&&aot.maxx[j]<=aot.maxx[q]&&aot.maxy[j]<=aot.maxy[q]&&aot.maxy[j]>=aot.miny[q])
                                        flag=0;
                                    else if(aot.maxx[q]>=aot.minx[j]&&aot.maxx[q]<=aot.maxx[j]&&aot.maxy[q]<=aot.maxy[j]&&aot.maxy[q]>=aot.miny[j])
                                        flag=0;
                                    else if(aot.maxx[j]>=aot.minx[q]&&aot.maxx[j]<=aot.maxx[q]&&aot.maxy[q]<=aot.maxy[j]&&aot.maxy[q]>=aot.miny[j])
                                        flag=0;
                                    else if(aot.maxx[q]>=aot.minx[j]&&aot.maxx[q]<=aot.maxx[j]&&aot.maxy[j]<=aot.maxy[q]&&aot.maxy[j]>=aot.miny[q])
                                        flag=0;
                                    if(flag==0)
                                        break;
                                }
                            if(flag==0)
                                break;
                        }
                    if(flag==0)
                        continue;
                    aot.area=0;
                    for(int q=0;q<k;q++)
                        if(aot.p[q]!=0)
                            aot.area+=(aot.maxx[q]-aot.minx[q])*(aot.maxy[q]-aot.miny[q]);
                    st.push(aot);
                }
        }
    }
    
    int main()
    {
        cin>>n>>k;
        int x[n],y[n];
        for(int i=0;i<n;i++)
            cin>>x[i]>>y[i];
        DFS(x,y);
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2018-08-08 08:27:12

    审题要仔细啊

    各个矩形之间不能相交

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=10000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    int n,m;
    int x[100],y[100];
    int b[100];
    int sum;
    bool empty[5];
    int c[5][5];
    int ans=inf;
    bool intersect(int a,int b) {
        int xx,yy;
        for (int i=1;i<=3;i+=2) {
            for (int j=2;j<=4;j+=2) {
                xx=c[b][i],yy=c[b][j];
                if (c[a][1]<=xx&&xx<=c[a][3])
                if (c[a][4]<=yy&&yy<=c[a][2]) return 1;
            }
        }
        return 0;
    }
    void dfs(int a) {
        if (a==n+1) {
            ans=min(ans,sum);
            return;
        }
        FOR(i,m) {
            b[a]=i;
            memset(empty,1,sizeof empty);
            FOR(j,m) c[j][1]=c[j][4]=inf,c[j][2]=c[j][3]=-inf;
            FOR(j,a) {
                empty[b[j]]=0;
                c[b[j]][1]=min(c[b[j]][1],x[j]);
                c[b[j]][2]=max(c[b[j]][2],y[j]);
                c[b[j]][3]=max(c[b[j]][3],x[j]);
                c[b[j]][4]=min(c[b[j]][4],y[j]);
            }
            bool ok=1;
            FOR(j,m) if (!empty[j]) FOR(jj,m) if (!empty[jj]) if (jj!=j) if (intersect(j,jj)) {
                ok=0;
                break;
            }
            if (!ok) continue;
            sum=0;
            FOR(j,m) if (!empty[j]) {
                sum+=(c[j][2]-c[j][4])*(c[j][3]-c[j][1]);
            }
            if (sum>ans) continue;
            dfs(a+1);
        }
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>m;
        FOR(i,n) cin>>x[i]>>y[i];
        
        dfs(1);
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2018-06-03 22:11:37

    AC200纪念!普普通通的 DFS+剪枝 就可以AC
    May the father of understanding guide U.

  • 0
    @ 2016-06-18 15:49:42

    枚举点在第几个矩形这个思路很好诶~~稍微剪一下枝就可以了~~
    ```c++
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<cstring>
    using namespace std;
    const int INF = 2147483647;

    struct Rec
    {
    int top,left,lower,right,size;
    bool isempty;
    Rec(int a=0,int b=0,int c=0,int d=0,int e=0,bool f=true) : top(a),left(b),lower(c),right(d),size(e),isempty(f) {};
    void size_update(){ size=(top-lower)*(right-left); }
    };

    struct Po
    {
    int x,y;
    Po(int a=0,int b=0) : x(a),y(b) {};
    bool operator< (const Po &a) const { return x<a.x || (x==a.x&&y<a.y); }
    };

    vector<Po> points;
    Rec rectangles[5];
    int n,k,ans=INF;

    inline int is_inside(int now)
    {
    int t=0;
    for(int i=1;i<=k;i++)
    if(!rectangles[i].isempty&&points[now].x>=rectangles[i].left&&points[now].x<=rectangles[i].right&&points[now].y>=rectangles[i].lower&&points[now].y<=rectangles[i].top) t++;
    return t;
    }

    void dfs(int now)
    {
    if(now==n)
    {
    int t=0;
    for(int i=1;i<=k;i++)
    if(!rectangles[i].isempty) t+=rectangles[i].size;
    ans=min(t,ans);
    return;
    }

    int t=0;
    for(int i=1;i<=k;i++)
    if(!rectangles[i].isempty) t+=rectangles[i].size;
    if(t>=ans) return;

    if(is_inside(now)) {dfs(now+1);return;}
    for(int i=1;i<=k;i++)
    {
    Rec temp=rectangles[i];
    if(rectangles[i].isempty)
    {
    rectangles[i].isempty=false;
    rectangles[i].left=rectangles[i].right=points[now].x;
    rectangles[i].top =rectangles[i].lower=points[now].y;
    rectangles[i].size_update();
    dfs(now+1);
    }
    else
    {
    if(points[now].x<rectangles[i].left) rectangles[i].left=points[now].x;
    else if(points[now].x>rectangles[i].right) rectangles[i].right=points[now].x;
    if(points[now].y>rectangles[i].top) rectangles[i].top=points[now].y;
    else if(points[now].y<rectangles[i].lower) rectangles[i].lower=points[now].y;
    rectangles[i].size_update();

    bool failed=false;
    for(int j=0;j<now;j++)
    if(is_inside(j)>1) { failed=true;break; }
    if(!failed) dfs(now+1);
    }
    rectangles[i]=temp;
    }
    }

    int main()
    {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    points.push_back(Po(a,b));
    }
    sort(points.begin(),points.end());

    dfs(0);
    printf("%d\n",ans);
    return 0;
    }
    ```

  • 0
    @ 2015-12-28 22:40:47

    总算AC了。0ms。
    说说思路:
    1. 枚举每个矩形的边界(只需枚举两个顶点即可)。O( k^(n*n) )
    2. 枚举每个点属于哪个矩形。O( n^k )

    一开始用思路一来做,超时+莫名其妙的1个WA
    改用思路2,秒杀。具体说来就是每次枚举点加入哪个矩形内,并把矩形相应扩大(也可能不扩大),递归搜索,搜完回来再恢复原始状态。注意的是每个矩形需要一个 isEmpty 标志,这样往里面加入第一个点的时候才不会出错。

    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>

    #define MAX(a,b) ((a)>(b)?(a):(b))
    #define MIN(a,b) ((a)<(b)?(a):(b))

    typedef struct{
    short isEmpty;
    int l, r, t, b; //left, right, top, bottom
    } RECT;
    typedef struct{
    int x, y;
    } POINT;

    int numPoint, numRect;
    int minArea = LONG_MAX;
    POINT point[55];
    RECT rect[5];

    void dfs(int index, int area);
    int intersect(RECT a, RECT b);
    int verify();

    int main(){
    int i;

    scanf("%d %d", &numPoint, &numRect);
    for(i=0; i<numPoint; i++)
    scanf("%d %d", &point[i].x, &point[i].y);
    for(i=0; i<numRect; i++)
    rect[i].isEmpty = 1;
    dfs(0, 0);
    printf("%d\n", minArea);

    return 0;
    }
    int intersect(RECT a, RECT b){ //see: http://blog.csdn.net/yahohi/article/details/7927158
    int dx, dy;
    dx = abs((a.r+a.l) - (b.r+b.l));
    dy = abs((a.t+a.b) - (b.t+b.b));
    if(dx <= a.r-a.l + b.r-b.l && dy <= a.t-a.b + b.t-b.b)
    return 1;
    return 0;
    }
    int verify(){ //if any two rectangles intersect, return false
    int i, k;
    for(i=0; i<numRect; i++){
    if(rect[i].isEmpty)
    continue;
    for(k=i+1; k<numRect; k++){
    if(rect[k].isEmpty)
    continue;
    if(intersect(rect[i], rect[k]))
    return 0;
    }
    }
    return 1;
    }
    void dfs(int index, int area){
    int i, delta;
    RECT tmp;
    if(area >= minArea)
    return;
    if(index == numPoint){
    for(i=0; i<numRect; i++){
    if(rect[i].isEmpty)
    return;
    }
    minArea = area;
    return;
    }
    for(i=0; i<numRect; i++){
    tmp = rect[i];
    if(rect[i].isEmpty){
    rect[i].l = rect[i].r = point[index].x;
    rect[i].b = rect[i].t = point[index].y;
    rect[i].isEmpty = 0;
    }else{
    rect[i].l = MIN(rect[i].l, point[index].x);
    rect[i].r = MAX(rect[i].r, point[index].x);
    rect[i].b = MIN(rect[i].b, point[index].y);
    rect[i].t = MAX(rect[i].t, point[index].y);
    }
    if(verify()){
    delta = (rect[i].r-rect[i].l) * (rect[i].t-rect[i].b); //new area
    delta -= (tmp.r-tmp.l) * (tmp.t-tmp.b); //-= original area
    dfs(index+1, area+delta);
    }
    rect[i] = tmp;
    }
    }

    • @ 2017-07-02 17:08:22

      不是n^k而是k^n吧

  • 0
    @ 2015-09-11 23:57:12

    记录信息

    评测状态 Accepted
    题目 P1126 矩形覆盖
    递交时间 2015-09-11 23:56:25
    代码语言 C++
    评测机 VijosEx
    消耗时间 17 ms
    消耗内存 564 KiB
    评测时间 2015-09-11 23:56:27

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 560 KiB, score = 10

    测试数据 #2: Accepted, time = 2 ms, mem = 564 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 564 KiB, score = 10

    Accepted, time = 17 ms, mem = 564 KiB, score = 50

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>

    using namespace std;

    int f[50 + 2][50 + 2][5];
    int n , k , i;

    struct point
    {
    int x , y;
    };

    point p[50 + 2];

    int dp( int l , int r , int k )
    {
    if( l > r )
    return 0;
    if( !k )
    return 100000000;
    if( k == 1 && f[l][r][k] == -1 )
    {
    if( l == r )
    return 0;
    int i , minx , miny , maxx , maxy;
    minx = miny = 10000000;
    maxx = maxy = 0;
    for( i = l ; i <= r ; i++ )
    {
    minx = min( minx , p[i].x );
    miny = min( miny , p[i].y );
    maxx = max( maxx , p[i].x );
    maxy = max( maxy , p[i].y );
    }
    return f[l][r][k] = ( maxx - minx ) * ( maxy - miny );
    }
    if( f[l][r][k] != -1 )
    return f[l][r][k];
    f[l][r][k] = 100000000;
    int i , j;
    for( i = l - 1 ; i <= r ; i++ )
    for( j = 0 ; j <= k ; j++ )
    f[l][r][k] = min( dp( l , i , j ) + dp( i + 1 , r , k - j ) , f[l][r][k] );
    return f[l][r][k];
    }

    inline int cmp( point a , point b )
    {
    if( a.y < b.y )
    return 1;
    if( a.y == b.y )
    if( a.x < b.x )
    return 1;
    return 0;
    }

    int main()
    {
    scanf( "%d %d" , &n , &k );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d %d" , &p[i].x , &p[i].y );
    sort( p + 1 , p + n + 1 , cmp );
    memset( f , -1 , sizeof( f ) );
    cout << dp( 1 , n , k ) << endl;
    return 0;
    }
    DP加上脏防卡AC的飞起

  • 0
    @ 2015-07-05 13:40:51

    放心做吧,裸搜都不会超时!

    var
    n,k,i:longint;
    x:array[0..51,1..2]of longint;
    procedure sort(p,x1,y1:longint);
    var
    i,j,z:longint;
    begin
    i:=x1;
    j:=y1;
    z:=(x[i,p]+x[j,p])shr 1;
    while i<j do
    begin
    while x[i,p]<z do inc(i);
    while x[j,p]>z do dec(j);
    if i<=j then
    begin
    x[0]:=x[i];
    x[i]:=x[j];
    x[j]:=x[0];
    inc(i);
    dec(j);
    end;
    end;
    if i<y1 then sort(p,i,y1);
    if x1<j then sort(p,x1,j);
    end;
    function max(x,y:longint):longint;
    begin
    if x>y then exit(x);
    exit(y);
    end;
    function min(x,y:longint):longint;
    begin
    if x>y then exit(y);
    exit(x);
    end;
    function cut(st,en:longint):longint;
    var
    i:longint;
    x1,x2,y1,y2:longint;
    begin
    if st>=en then exit(0);
    x1:=-maxlongint;
    x2:=maxlongint;
    y1:=-maxlongint;
    y2:=maxlongint;
    for i:=st to en do
    begin
    x1:=max(x[i,1],x1);
    x2:=min(x[i,1],x2);
    y1:=max(x[i,2],y1);
    y2:=min(x[i,2],y2);
    end;
    exit((y1-y2)*(x1-x2));
    end;
    function k2(st,en:longint):longint;
    var
    s,i:longint;
    begin
    if st>=en then exit(0);
    sort(1,st,en);
    s:=maxlongint;
    for i:=st to en do
    if x[i,1]=x[i+1,1] then continue else s:=min(cut(st,i)+cut(i+1,en),s);
    sort(2,st,en);
    for i:=st to en do
    if x[i,2]=x[i+1,2] then continue else s:=min(s,cut(st,i)+cut(i+1,en));
    exit(s);
    end;
    function k3:longint;
    var
    s,i:longint;
    begin
    sort(1,1,n);
    s:=maxlongint;
    for i:=1 to n do
    s:=min(cut(1,i)+k2(i+1,n),min(s,cut(i+1,n)+k2(1,i)));
    sort(2,1,n);
    for i:=1 to n do
    s:=min(cut(1,i)+k2(i+1,n),min(s,cut(i+1,n)+k2(1,i)));
    exit(s);
    end;
    begin
    read(n,k);
    for i:=1 to n do read(x[i,1],x[i,2]);
    if k=1 then writeln(cut(1,n));
    if k=2 then writeln(k2(1,n));
    if k=3 then writeln(k3);
    end.

  • 0
    @ 2014-10-05 07:37:44

    type rectangle=record
    xl,xr,yu,yd:longint;
    end;
    arr=array[1..4] of rectangle;

    var a:arr;
    px,py:array[1..50] of longint;
    b:array[1..50] of boolean;
    n,i,min,k,s,ss,tot,sb:longint;

    function maxnum(a,b:longint):longint;
    begin
    maxnum:=a;
    if a<b then
    maxnum:=b;
    end;

    function minnum(a,b:longint):longint;
    begin
    minnum:=a;
    if a>b then
    minnum:=b;
    end;

    function area(var t:rectangle):longint;
    begin
    with t do
    exit((xr-xl)*(yu-yd));
    end;

    function pointinit(var x,y:longint; var t:rectangle):boolean;
    begin
    with t do
    if (x>=xl)and(x<=xr)and(y>=yd)and(y<=yu) then
    exit(true)
    else
    exit(false);
    end;

    function cover(var t:rectangle):longint;
    var i:longint;
    begin
    cover:=0;
    for i:=1 to n do
    if not b[i] and pointinit(px[i],py[i],t) then
    begin
    b[i]:=true;
    inc(cover);
    end;
    end;

    procedure discover(var t,r:rectangle);
    var i:longint;
    begin
    for i:=1 to n do
    if b[i] and pointinit(px[i],py[i],t) and not pointinit(px[i],py[i],r) then
    b[i]:=false;
    end;

    function check(x:longint; var a:arr):boolean;
    var i:longint;
    begin
    with a[x] do
    for i:=1 to tot do
    begin
    if x<>i then
    if (maxnum(xl,a[i].xl)<=minnum(xr,a[i].xr))and(maxnum(yd,a[i].yd)<=minnum(yu,a[i].yu)) then
    exit(false);
    end;
    exit(true);
    end;

    function putpoint(x,y:longint; var t:rectangle):boolean;
    begin
    putpoint:=false;
    with t do
    begin
    if (xl<0)or(xr<0)or(yu<0)or(yd<0) then
    begin
    xl:=x;
    xr:=x;
    yu:=y;
    yd:=y;
    inc(tot);
    exit(true);
    end;
    if x<xl then
    xl:=x;
    if x>xr then
    xr:=x;
    if y>yu then
    yu:=y;
    if y<yd then
    yd:=y;
    end;
    end;

    procedure search(ar,covered,pos:longint; a:arr);
    var i,j:longint;
    t,x:rectangle;
    bo:boolean;
    begin
    if n-covered<k-tot then
    exit;
    if covered>=n then
    begin
    if ar<min then
    min:=ar;
    end
    else
    begin
    if not b[pos] then
    for i:=1 to minnum(tot+1,k) do
    begin
    t:=a[i];
    bo:=putpoint(px[pos],py[pos],a[i]);
    if check(i,a) then
    begin
    s:=area(a[i])-area(t);
    ss:=cover(a[i]);
    search(ar+s,covered+ss,pos+1,a);
    discover(a[i],t);
    end;
    if bo then
    dec(tot);
    a[i]:=t;
    end
    else
    search(ar,covered,pos+1,a);
    end;
    end;

    begin
    readln(n,k);
    for i:=1 to n do
    readln(px[i],py[i]);
    min:=maxlongint;
    tot:=0;
    for i:=1 to k do
    begin
    a[i].xl:=-1;
    a[i].xr:=-1;
    a[i].yu:=-1;
    a[i].yd:=-1;
    end;
    search(0,0,1,a);
    writeln(min);
    end.

  • 0
    @ 2014-08-10 15:19:23

    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>

    #define M 101
    #define INF 0x7fffffff

    using namespace std;

    int n,m;
    int fx[M],fy[M];
    int minxx=INF;

    struct node
    {
    int minx;
    int miny;
    int maxx;
    int maxy;
    }str1[M];

    void init()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    fx[i]=x;
    fy[i]=y;
    }
    for(int i=1;i<=m;i++)
    {
    str1[i].minx=1000;
    str1[i].miny=1000;
    str1[i].maxx=-100;
    str1[i].maxy=-100;
    }
    }

    int com()
    {
    int flag=0;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    if(i!=j)
    {
    if(str1[i].minx>=str1[j].minx&&str1[i].minx<=str1[j].maxx&&str1[i].miny>=str1[j].miny&&str1[i].miny<=str1[j].maxy)
    flag=1;
    if(str1[i].minx>=str1[j].minx&&str1[i].minx<=str1[j].maxx&&str1[i].maxy>=str1[j].miny&&str1[i].maxy<=str1[j].maxy)
    flag=1;
    if(str1[i].maxx>=str1[j].minx&&str1[i].maxx<=str1[j].maxx&&str1[i].miny>=str1[j].miny&&str1[i].miny<=str1[j].maxy)
    flag=1;
    if(str1[i].maxx>=str1[j].minx&&str1[i].maxx<=str1[j].maxx&&str1[i].maxy>=str1[j].miny&&str1[i].maxy<=str1[j].maxy)
    flag=1;
    }
    int sum=0;
    for(int i=1;i<=m;i++)
    {
    if(str1[i].minx==1000&&str1[i].miny==1000&&str1[i].maxx==-100&&str1[i].maxy==-100)
    sum=sum+0;
    else
    sum=sum+(str1[i].maxx-str1[i].minx)*(str1[i].maxy-str1[i].miny);
    }
    if(sum>=minxx)
    flag=1;
    return flag;
    }

    void dfs(int no)
    {
    if(com()==1)
    return ;
    if(no==n+1)
    {
    int flag=0;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    if(i!=j)
    {
    if(str1[i].minx>=str1[j].minx&&str1[i].minx<=str1[j].maxx&&str1[i].miny>=str1[j].miny&&str1[i].miny<=str1[j].maxy)
    flag=1;
    if(str1[i].minx>=str1[j].minx&&str1[i].minx<=str1[j].maxx&&str1[i].maxy>=str1[j].miny&&str1[i].maxy<=str1[j].maxy)
    flag=1;
    if(str1[i].maxx>=str1[j].minx&&str1[i].maxx<=str1[j].maxx&&str1[i].miny>=str1[j].miny&&str1[i].miny<=str1[j].maxy)
    flag=1;
    if(str1[i].maxx>=str1[j].minx&&str1[i].maxx<=str1[j].maxx&&str1[i].maxy>=str1[j].miny&&str1[i].maxy<=str1[j].maxy)
    flag=1;
    }
    for(int i=1;i<=m;i++)
    if(str1[i].minx>str1[i].maxx||str1[i].miny>str1[i].maxy)
    flag=1;
    if(flag==0)
    {
    int sum=0;
    for(int i=1;i<=m;i++)
    sum=sum+(str1[i].maxx-str1[i].minx)*(str1[i].maxy-str1[i].miny);
    minxx=min(minxx,sum);
    }
    }
    else
    for(int i=1;i<=m;i++)
    {
    int x1=str1[i].minx;
    int y1=str1[i].miny;
    int x2=str1[i].maxx;
    int y2=str1[i].maxy;
    if(fx[no]<str1[i].minx)
    str1[i].minx=fx[no];
    if(fx[no]>str1[i].maxx)
    str1[i].maxx=fx[no];
    if(fy[no]<str1[i].miny)
    str1[i].miny=fy[no];
    if(fy[no]>str1[i].maxy)
    str1[i].maxy=fy[no];
    dfs(no+1);
    str1[i].minx=x1;
    str1[i].miny=y1;
    str1[i].maxx=x2;
    str1[i].maxy=y2;
    }
    }

    int main()
    {
    init();
    dfs(1);
    printf("%d\n",minxx);
    return 0;
    }

  • 0
    @ 2013-11-06 21:46:46

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define Max 1000000
    using namespace std;

    int n,m,ans=Max,x[52],y[52],f[52][52][5]={0};

    int High(int i,int j){
    int maxh=0,minh=1000,temp=i;
    while(temp<=j)
    maxh=max(maxh,y[temp++]);
    temp=i;
    while(temp<=j)
    minh=min(minh,y[temp++]);
    return maxh-minh;
    }

    void Dp(){
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=2;k<=m;++k)
    f[i][j][k]=Max;

    for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    f[i][j][1]=(x[j]-x[i])*High(i,j);
    for(int i=1;i<=n;++i)
    for(int k=1;k<=m;++k)
    f[i][i][k]=0;

    for(int k=2;k<=m;++k)
    for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    for(int l=i+1;l<=j;++l)
    f[i][j][k]=min(f[i][j][k],f[i][l-1][k-1]+(x[j]-x[l])*High(l,j));

    ans=min(ans,f[1][n][m]);
    }

    int main()
    {
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    cin>>x[i]>>y[i];

    for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}
    else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);

    Dp();

    for(int i=1;i<=n;++i)
    swap(x[i],y[i]);

    for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}
    else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);

    Dp();

    cout<<ans<<endl;
    return 0;

    }

  • 0
    @ 2013-10-07 21:22:02

    procedure Dynamic;
    var
    j,k,p:integer;
    s:array[1..50,1..50] of longint;
    f:array[1..50,1..50,1..4] of longint;
    begin
    for i:=1 to m do
    for j:=1 to m do
    for k:=1 to n do
    f[i,j,k]:=300000;
    for i:=1 to m do
    for j:=i to m do
    begin
    s[i,j]:=(x[j]-x[i])*hight(i,j);
    f[i,j,1]:=s[i,j];
    end;
    for p:=1 to m do
    for i:=1 to m-p do
    begin
    j:=i+p;
    for k:=2 to n do
    for t:=i to j-1 do
    f[i,j,k]:=min(f[i,j,k],f[i,t,k-1]+s[t+1,j]);
    end;
    ans:=min(ans,f[1,m,n]);
    end;
    begin
    readln(m,n);
    for i:=1 to m do
    readln(x[i],y[i]);
    x[m+1]:=maxint;y[m+1]:=maxint;
    ans:=maxlongint;
    sort(1,m);
    t:=x[1];last:=1;
    for i:=2 to m+1 do
    if x[i]<>t then
    begin
    qsort(last,i-1);
    t:=x[i];
    last:=i;
    end;
    Dynamic;
    for i:=1 to m do
    begin
    t:=x[i];
    x[i]:=y[i];
    y[i]:=t;
    end;
    sort(1,m);
    t:=x[1];last:=1;
    for i:=2 to m+1 do
    if x[i]<>t then
    begin
    qsort(last,i-1);
    t:=x[i];
    last:=i;
    end;
    Dynamic;
    writeln(ans);
    end.

  • 0
    @ 2009-11-08 11:52:28

    编译通过...

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

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

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

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

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

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

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

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

    编了60多行,搞得我头大。

  • 0
    @ 2009-11-06 11:19:58

    汗,自己机器上运行明明每个点都秒杀

    结果同一个程序交上去,第一次两个点超时,第2次1个点超时,第三次全部超时,。。。

  • 0
    @ 2009-11-04 16:01:28

    切分的方法有很多种,但是有些是重复的,可以通过旋转点的坐标减少判断的情况

    最终 K=1时只有一种情况

    K=2时有也只有一种情况

    K=3时只有两种情况

    K=4时有五种

    划分的复杂度是 O(n^(K-1)),划分好了后算每一块面积是 O(K),总复杂度O(n^K)

    此题最大为50^4,完全合适

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    #define INF 2100000000

    #define MIN(A,B) ((A)(B)?(A):(B))

    #define ABS(A) ((A)

  • 0
    @ 2009-11-01 21:15:01

    据说贪心都能过~

    我就一五一十枚举过去171行

    敝程序优点就是过程比较多,思路比较清晰

    const maxn=1000000;

    var n,k,i:longint;

    a,b:array[1..50] of longint;

    function min(x,y:longint):longint;

    begin

    if x>y then exit(y) else exit(x);

    end;

    function min1(s,t:longint):longint;

    var i:longint;

    begin

    min1:=maxn;

    for i:=s to t do if a[i]max2 then max2:=b[i];

    end;

    procedure soapa(s,t:longint);

    var i,j,m:longint;

    begin

    for i:=s to t-1 do

    for j:=s to t-i do

    if a[j]>a[j+1] then

    begin

    m:=a[j];

    a[j]:=a[j+1];

    a[j+1]:=m;

    m:=b[j];

    b[j]:=b[j+1];

    b[j+1]:=m;

    end;

    end;

    procedure soapb(s,t:longint);

    var i,j,m:longint;

    begin

    for i:=s to t-1 do

    for j:=s to t-i do

    if b[j]>b[j+1] then

    begin

    m:=a[j];

    a[j]:=a[j+1];

    a[j+1]:=m;

    m:=b[j];

    b[j]:=b[j+1];

    b[j+1]:=m;

    end;

    end;

    function g(s,t:longint):longint;

    var x1,x2,y1,y2:longint;

    begin

    x1:=min1(s,t);

    x2:=max1(s,t);

    y1:=min2(s,t);

    y2:=max2(s,t);

    g:=(x2-x1)*(y2-y1);

    end;

    function g21(s,t:longint):longint;

    var t1,t2,ans,i:longint;

    begin

    soapa(s,t);

    ans:=maxn;

    for i:=s to t-1 do

    begin

    t1:=g(s,i);

    t2:=g(i+1,t);

    if t1+t2

  • 0
    @ 2009-10-23 15:31:31

    编译通过...

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

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

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

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

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

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

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

    ....1 time....

    Yeah!

  • 0
    @ 2009-10-04 19:43:13

    看了这题目,没什么太大的想法,直接弱弱的想到快排+枚举.....

    顺便判断了一下可能重合的情况,交上去,1遍AC........

    可是回头想想,发现好多情况还没考虑,程序压根就是错的......

    无语了,这样的数据....还是重头再做一次吧.....

    Ps:如果NOIP2009的数据也是~~

  • 0
    @ 2009-09-10 11:48:41

    看了LRJ的报告200+的CODE我晕了……

    他用的切割法,K=3有5种切割……

    K=4有22种!!……

    (我很想知道如果K=4的话能用什么办法做。离散化么?)

    后来发现没有K=4,50^3还好没什么问题。

  • 0
    @ 2009-09-09 07:43:18

    program dd;

    var x,y:array[1..50] of longint;

    i,j,k,l,m,n,s,sum,ans,x1,x2,y1,y2,min,o:longint;

    procedure qsort1(v,w:longint);

    var g,t,s,l,r:longint;

    begin

    t:=x[(v+w) div 2];l:=v;r:=w;

    s:=y[(v+w) div 2];

    repeat

    while (x[l]s)) do dec(r);

    if lr;

    if l

信息

ID
1126
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1152
已通过
488
通过率
42%
上传者