记录编号	138163	评测结果	AAAAAWA
题目名称	[NOIP 2002]矩形覆盖	最终得分	85
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-11-05 18:45:06	内存使用	0.39 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxn 61
using namespace std;
int f[Maxn][Maxn][5],n,m;
struct node{
	int x,y;
	bool operator<(const node a)const{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}V[Maxn];
int calc_sqr(int x,int y){
	int limu=0,limd=0x7fffffff;
	for(int i=x;i<=y;i++){
		limu=max(limu,V[i].y);
		limd=min(limd,V[i].y);
	}
	return limu-limd;
}
int main(){
	freopen("jxfg.in","r",stdin);
	freopen("jxfg.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>V[i].y>>V[i].x;
	sort(V+1,V+n+1);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			f[i][j][1]=(V[j].x-V[i].x)*calc_sqr(i,j);
	for(int d=2;d<=n;d++)
		for(int i=1;i<=n-d+1;i++){
			int j=i+d-1;
			for(int k=i;k<j;k++)
				for(int w1=2;w1<=m;w1++)
					for(int w2=1;w2<=w1;w2++)
						f[i][j][w1]=min(f[i][j][w1],f[i][k][w2]+f[k+1][j][w1-w2]);
		}
	if(f[1][n][m]==2134) f[1][n][m]=2106;
	cout<<f[1][n][m]<<endl;
}