在平面上有 n 个点（n <= 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。

　　这些点可以用 k 个矩形（1<=k<=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。

输入格式

n k

xl y1

x2 y2

... ...

xn yn （0<=xi,yi<=500)

输出格式

一个整数，即满足条件的最小的矩形面积之和。

 

 

第一次作到该种DP题，思维很新颖。

将点按x为第一关键字，y为第二关键字，递增排序。

f[i][j][k]表示 由点 i 到点 j范围之内分成 k 个矩形最少面积。

1 #include
     
       2 #define Max 1000000 3 using namespace std; 4  5 int n,m,ans=Max,x[52],y[52],f[52][52][5]={
   0}; 6  7 int High(int i,int j){ 8     int maxh=0,minh=1000,temp=i; 9     while(temp<=j)10     maxh=max(maxh,y[temp++]);11     temp=i;12     while(temp<=j)13     minh=min(minh,y[temp++]);14     return maxh-minh;15     }16 17 18 void Dp(){19      for(int i=1;i<=n;++i)20      for(int j=1;j<=n;++j)21      for(int k=2;k<=m;++k)22      f[i][j][k]=Max;23      24      for(int i=1;i<=n;++i)25      for(int j=i+1;j<=n;++j)26      f[i][j][1]=(x[j]-x[i])*High(i,j);27      for(int i=1;i<=n;++i)28      for(int k=1;k<=m;++k)29      f[i][i][k]=0;30      31      for(int k=2;k<=m;++k)32      for(int i=1;i<=n;++i)33      for(int j=i+1;j<=n;++j)34      for(int l=i+1;l<=j;++l)35      f[i][j][k]=min(f[i][j][k],f[i][l-1][k-1]+(x[j]-x[l])*High(l,j));36 37      ans=min(ans,f[1][n][m]);38      }39 40 int main()41 {42     cin>>n>>m;43     for(int i=1;i<=n;++i)44     cin>>x[i]>>y[i];45     46     for(int i=1;i<=n;++i)47     for(int j=i+1;j<=n;++j)48     if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}49     else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);50     51     Dp();    52     53     for(int i=1;i<=n;++i)54     swap(x[i],y[i]);55     56     for(int i=1;i<=n;++i)57     for(int j=i+1;j<=n;++j)58     if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}59     else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);60     61     Dp();    62     63     cout<
      
       <