NOIP2002 矩形覆盖

题四矩形覆盖（存盘名NOIPG4）

[问题描述]:

　　在平面上有 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)

[输出]:

　　输出至屏幕。格式为：

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

[输入输出样例]

d.in :

　4 2

　1 1

　2 2

　3 6

　0 7

屏幕显示：

【思路】

回溯法。

搜索依次确定每个点属于哪一个矩形，时间复杂度为O(50^4)。最优解剪枝+如果相交则剪枝。

在网上看到了DP的做法:

f[i][j][k]=min{ f[i][l][k-1]+S(l+1,j) }

　算法并不完美（只出现了矩形包含的点连续的情况，还有可能不连续），因为数据比较弱所以才能AC，但不失为一种可以借鉴的思路。

【dfs代码】

 #include<iostream>

 #include<cstring>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std; 

 const int maxn = +;

 struct Matrix{

     int a,b,c,d;

     bool flag;

     Matrix() { flag=false; }

 }re[];

 int x[maxn],y[maxn];

 int n,m,ans;

 bool in(int x,int y,Matrix A) {

     return (x>=A.a && x<=A.b && y>=A.c && y<=A.d);

 }

 bool can(int i,int j) {

     bool ans=;

     if(in(re[i].a,re[i].c,re[j])) return ;

     if(in(re[i].a,re[i].d,re[j])) return ;

     if(in(re[i].b,re[i].c,re[j])) return ;

     if(in(re[i].b,re[i].d,re[j])) return ;

     return ;

 }

 void dfs(int d) {

     Matrix tmp;

     int sum=;

     FOR(i,,m)

       if(re[i].flag)

       {

           sum += (re[i].b-re[i].a)*(re[i].d-re[i].c);

           FOR(j,i+,m)

              if(re[j].flag && (can(i,j))) return ;

       }

     if(sum>=ans) return ;

     if(d>n) {  ans=sum; return ; }

     FOR(i,,m) {

         tmp=re[i];

         if(!re[i].flag) {

             re[i].flag=;

             re[i].a=re[i].b=x[d];

             re[i].c=re[i].d=y[d];

         }

         else {

             re[i].a=min(re[i].a,x[d]);

             re[i].b=max(re[i].b,x[d]);

             re[i].c=min(re[i].c,y[d]);

             re[i].d=max(re[i].d,y[d]);

         }

         dfs(d+);

         re[i]=tmp;

     }

 }

 int main() {

     ios::sync_with_stdio(false);

     cin>>n>>m;

     FOR(i,,n)  cin>>x[i]>>y[i];

     ans=1e9;

     dfs();

     cout<<ans;

     return ;

 }

【dp代码】

 #include<iostream>

 #define Max 1000000

 using namespace std;

 int n,m,ans=Max,x[],y[],f[][][]={};

 int High(int i,int j){

     int maxh=,minh=,temp=i;

     while(temp<=j)

     maxh=max(maxh,y[temp++]);

     temp=i;

     while(temp<=j)

     minh=min(minh,y[temp++]);

     return maxh-minh;

 }

 void Dp(){

      for(int i=;i<=n;++i)

      for(int j=;j<=n;++j)

      for(int k=;k<=m;++k)

      f[i][j][k]=Max;

      for(int i=;i<=n;++i)

      for(int j=i+;j<=n;++j)

      f[i][j][]=(x[j]-x[i])*High(i,j);

      for(int i=;i<=n;++i)

      for(int k=;k<=m;++k)

      f[i][i][k]=;

      for(int k=;k<=m;++k)

      for(int i=;i<=n;++i)

      for(int j=i+;j<=n;++j)

      for(int l=i+;l<=j;++l)

      f[i][j][k]=min(f[i][j][k],f[i][l-][k-]+(x[j]-x[l])*High(l,j));

      ans=min(ans,f[][n][m]);

 }

 int main()

 {

     cin>>n>>m;

     for(int i=;i<=n;++i)

     cin>>x[i]>>y[i];

     for(int i=;i<=n;++i)

     for(int j=i+;j<=n;++j)

     if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}

     else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);

     Dp();    

     for(int i=;i<=n;++i)

     swap(x[i],y[i]);

     for(int i=;i<=n;++i)

     for(int j=i+;j<=n;++j)

     if(x[i]>x[j]) {swap(x[i],x[j]);swap(y[i],y[j]);}

     else if(x[i]==x[j]&&y[i]>=y[j]) swap(y[i],y[j]);

     Dp();    

     cout<<ans<<endl;

     return ;

     }

巴特西

NOIP2002 矩形覆盖

最新文章

热门文章