(something~else:)
看了一圈似乎没人用我的方法，有点小激动的我连忙跑过来码了份题解
(ps:CSP2019~RP++)
开始讲题
看到数据范围是很水的(n<=50,k<=4)，顿时感觉出题人良心，可以简单的想到应该有个(O(n^4))的正常算法
(first)
关键是怎么利用矩形的问题。
对于矩形的确定，我们不能简单地被标题给带过去看成是“覆盖”了，其实换个角度想，矩形的覆盖可以看做矩形的“划分”
比如用(k)个矩形覆盖所有点，就是(k-1)划分整个图形使其成为(k)个矩形
(second)
想到划分的话就很容易想到可以有状态方程的设计：
令(f_{d1,d2,e1,e2,k})为横坐标上下界分别为(d2,d1)，纵坐标上下界分别为(e1,e2)的点集划分(k)次的矩形覆盖面积最小值，则：
[f_{d1,d2,e1,e2,k}=min(minlimits_{iin[d1,d2],jin[0,k)}(f_{d1,i,e1,e2,k-j-1}+f_{i+1,d2,e1,e2,j}),minlimits_{iin[e1,e2],jin[0,k)}(f_{d1,d2,e1,i,k-j-1}+f_{d1,d2,i+1,e2,j}))
]
[ ext{边界：}f_{d1,d2,e1,e2,0}= ext{d1,d2,e1,e2内的点集的面积（这个应该都会算哈）}
]
[ ext{目标：}f_{min_x,max_x,min_y,max_y,k-1} ext{这里的k是矩形数}
]
关于(x_i,y_iin[0,500])可以离散化一下，这样就成功将复杂度化为(O(n^4))
(third)
祝大家(CSP2019~RP++)
(forth)
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x*f;
}
const int xx=52;
struct point
{
int x,y;
}d[xx],e[xx];
int ans=0x7fffffff,n;
inline bool cmp1(point a,point b){return a.x<b.x;}
inline bool cmp2(point a,point b){return a.y<b.y;}
inline int div(int d1,int d2,int e1,int e2,int k)
{
int res=ans;
if(k)
{
for(register int i=d1;i<d2;++i)
for(register int j=0;j<k;++j)
res=min(res,div(d1,i,e1,e2,k-j-1)+div(i+1,d2,e1,e2,j));
for(register int i=e1;i<e2;++i)
for(register int j=0;j<k;++j)
res=min(res,div(d1,d2,e1,i,k-j-1)+div(d1,d2,i+1,e2,j));
return res;
}
int mxx=0,mnx=ans,mxy=0,mny=ans;
for(register int i=1;i<=n;++i)
if(d[i].x>=d[d1].x&&d[i].x<=d[d2].x)
if(d[i].y>=e[e1].y&&d[i].y<=e[e2].y)
mxx=d[i].x,mnx=min(mnx,d[i].x),mxy=max(mxy,d[i].y),mny=min(mny,d[i].y);
return (mxy-mny)*(mxx-mnx);
}
int main()
{
n=read();int k=read();
for(register int i=1;i<=n;i++) d[i]=e[i]=(point){read(),read()};
sort(d+1,d+n+1,cmp1);
sort(e+1,e+n+1,cmp2);
ans=div(1,n,1,n,k-1);
printf("%d
",ans);
return 0;
}