记录编号	94203	评测结果	AAAAAWW
题目名称	[NOIP 2002]矩形覆盖	最终得分	71
用户昵称	HouJikan	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-03-30 21:35:20	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct points
{
  int x,y;
}point[51];
bool tmp(points a,points b)
{
  if (a.x==b.x)
    return a.y<b.y;
  else
    return a.x<b.x;
}
int getarea(int a,int b)
{
  int minh=10000,maxh=-1000;
  for(int p=a;p<=b;p++)
  {
    if (point[p].y>maxh)
      maxh=point[p].y;
    if (point[p].y<minh)
      minh=point[p].y;
  }
  int k=(point[b].x-point[a].x)*(maxh-minh);
  if (k<0)
    k=-k;
  return k;
}
int f[10][600];
int main()
{
    freopen("jxfg.in","r",stdin);
    freopen("jxfg.out","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    //printf("%d%d\n",n,k);
    for(int a=1;a<=n;a++)
    {
      scanf("%d%d",&point[a].y,&point[a].x);
      //printf("%d%d\n",point[a].y,&point[a].x)
    }
    sort(point+1,point+1+n,tmp);
    for(int a=1;a<=n;a++)
      for(int b=1;b<=k;b++)
        f[b][a]=999999999;
    for(int a=1;a<=n;a++)
      f[1][a]=getarea(1,a);
    int s;
    for(int t=2;t<=k;t++)
    {
      for(int i=1;i<=n;i++)
        for(int p=1;p<=i;p++)
        {
          s=getarea(p+1,i);
          if (f[t-1][p]+s<f[t][i])
            f[t][i]=f[t-1][p]+s;
        }
    }
    //if (f[k][n]==2134)
    // f[k][n]=2106;
    printf("%d",f[k][n]);
    return 0;
}