上代码

#include<bits/stdc++.h>
using namespace std;
const int N=55,K=5,inf=2e9+500,ts=25e6;
int n,k,s=inf,cnt=0;
struct node
{
    int x,y;
}a[N];
struct node2
{
    int x=inf,y=inf,x2=-inf,y2=-inf,s=0;
}b[K];
void work(node2 &a,node b) //让矩形a包含b点
{
    a.x=min(a.x,b.x);
    a.y=min(a.y,b.y);
    a.x2=max(a.x2,b.x);
    a.y2=max(a.y2,b.y);
    a.s=(a.x2-a.x)*(a.y2-a.y);
}
bool ask(node2 a,node2 b) //a b矩形是否相交
{
    int x,y;
    for(int i=0;i<4;i++)
    {
        x=(i%2?a.x:a.x2);
        y=(i/2?a.y:a.y2);
        if(b.x<=x&&x<=b.x2&&b.y<=y&&y<=b.y2)
            return false;
    }
    return true;
}
void dfs(int x)
{
    if(cnt>=ts) return; //要超时 退出
    if(x==n+1)
    {
        ++cnt;
        bool have=true;
        for(int i=1;i<k;i++)
            for(int j=0;j<i;j++)
                have&=ask(b[j],b[i]); //所有矩形是否两两不相交
        int sum=0;
        for(int i=0;i<k;i++) sum+=b[i].s;
        /*cout<<have<<endl;
        for(int i=0;i<k;i++)
            cout<<b[i].x<<" "<<b[i].y<<" "<<b[i].x2<<" "<<b[i].y2<<" "<<b[i].s<<endl;
        cout<<endl;*/
        if(have) s=min(s,sum);
        return;
    }
    node2 s;
    for(int i=0;i<k;i++)
    {
        s=b[i];
        work(b[i],a[x]);
        dfs(x+1);
        b[i]=s;
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    work(b[0],a[1]);
    dfs(2);
    cout<<s<<endl;
}

传送门

思路和题解一样 但跑的比题解慢很多

时间复杂度$O(k^{n+1})$ 按题目数据范围不能过 但题解为什么能过呢QWQ

附上题解 作者:saxiy

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

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() {
	scanf("%d%d", &n, &k);
	for(int i = 0;i < n;i++)
		scanf("%d%d", x + i, y + i);
	dfs(0, 0);
	printf("%d", ans);
	return 0;
}

QWQ 谢谢