poj 2836 Rectangular Covering-白红宇

poj 2836 Rectangular Covering

阅读量：4113 次

发布时间：2019-05-25

本文共 1432 字，大约阅读时间需要 4 分钟。

题意：给你n个点的坐标，求覆盖所有顶点的最小矩形面积（每个矩形至少覆盖两个顶点）

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; const int mod=100000000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a
               
                =lx&&x[k]<=rx&&y[k]>=dy&&y[k]<=uy) state[i][j]|=(1<<(k-1)); state[j][i]=state[i][j]; area[j][i]=area[i][j]; } for(int k=0;k<=(1<

分析：一开始想的是直接在图上进行状态压缩，用1表示这一层覆盖，再一层一层扫下来结果想不出来，因为这个

围成矩形不再单单是一层的问题了。

正确的做法是强大的建模，每两个顶点之间建立一个矩形，保存这个矩形的面积和覆盖的顶点，然后

dp[j]表示在当前覆盖顶点的情况为j的情况下的最小的面积，暴力枚举就好。

ps:貌似直接数组做比用结构体要简洁

wa代码：

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; const int mod=100000000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a
               
                =l&&p[k].x<=r&&p[k].y>=d&&p[k].y<=u) { int m=ar[j].fu; dp[m|(1<<(k-1))]=min(dp[m|(1<<(k-1))],dp[m]); } } for(int j=0;j<=(1<