#include<bits/stdc++.h>
using namespace std;
#define N 55

int n,k,x[N],y[N],ans=INT_MAX>>2;
struct mat{
    int lx,ly,rx,ry;
    bool cnt;
    void add(int x, int y){
        if(!cnt){
            lx=rx=x;
            ly=ry=y;
            cnt = 1;
        }
        else{
            if(x<lx)
                lx = x;
            else if(x>rx)
                rx = x;
            if(y>ly)
                ly = y;
            else if(y<ry)
                ry = y;
        }
    }
    bool inmat(int x, int y) const {
        return lx<=x && x<=rx && ry<=y && y<=ly;
    }
    int operator() () {
        if(!cnt)
            return 0;
        return (rx-lx)*(ly-ry);
    }
    bool operator* (const mat &o){
        if(!cnt || !o.cnt)
            return 0;
        return o.inmat(lx, ly) || o.inmat(lx, ry) || o.inmat(rx, ly) || o.inmat(rx, ry);
    }
}km[5];

bool check(){
    for(int i=1; i<=k; i++)
        for(int j=i+1; j<=k; j++)
            if(km[i]*km[j])
                return 0;
    return 1;
}

void dfs(int i,int area) {
    if(area>=ans)
        return;
    if(i==n){
        if(check())
            if(ans>area)
                ans=area;
        return;
    }
    mat tmp;
    for(int j=1; j<=k; j++){
        tmp=km[j];
        km[j].add(x[i],y[i]);
        dfs(i+1,area-tmp()+km[j]());
        km[j]=tmp;
    }
}

int main() {
    cin>>n>>k;
    for(int i=0; i<n; i++)
        scanf("%d%d",x+i,y+i);
    dfs(0,0);
    cout<<ans;
    return 0;
}

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;
}

审题要仔细啊

各个矩形之间不能相交

#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;
}

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

枚举点在第几个矩形这个思路很好诶～～稍微剪一下枝就可以了～～
```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;
}
```

总算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;
}
}

记录信息

评测状态 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的飞起

放心做吧，裸搜都不会超时！

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.

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.

#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;
}

#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;

}

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.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

最终 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)

据说贪心都能过~

我就一五一十枚举过去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

编译通过...

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

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

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

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

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

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

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

....1 time....

Yeah!

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

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

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

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

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

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

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

K=4有22种！！……

（我很想知道如果K=4的话能用什么办法做。离散化么？）

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