hdu 1937 Finding Seats 尺取法-白红宇

hdu 1937 Finding Seats 尺取法

阅读量：4073 次

发布时间：2019-05-25

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

这道题主要就是选一个对角矩阵，使得其内的可用座位》=k,求满足这个条件的最小矩阵面积

三重循环加优化，最内层为尺取法，复杂度大概为300；

故空间复杂度为300^3，不会超时，同时第三层内的搜索与判断都应为加法级别的；

第一次打的时候判断一个区域内的可用座位是暴力搜索，最麻烦的时候复杂度达到300^5，。。超时

看了其他人的代码才明白；

先进行一个对矩阵内可用座位的预处理，复杂度为300^2；

故代码的复杂度可理解为300^3+300^2，比我都300^3*300^2快的不是一个级别

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int INF=1<<31-1;char a[310][310];int mmap[310][310];int r,c,k;void chuli(){    int i,j;    for(i=1;i<=r;i++)        mmap[i][1]=(a[i][1]=='.');    for(j=1;j<=c;j++)        mmap[1][j]=(a[1][j]=='.');    for(i=1;i<=r;i++)    {        for(j=1;j<=c;j++)        {            mmap[i][j]=(mmap[i-1][j]+mmap[i][j-1]-mmap[i-1][j-1]+(a[i][j]=='.'));        }    }}int check(int x1,int y1,int x2,int y2){    if(mmap[x2][y2]+mmap[x1-1][y1-1]-mmap[x1-1][y2]-mmap[x2][y1-1]>=k)        return 0;    else        return 1;}int main(){    while(scanf("%d%d%d",&r,&c,&k)!=EOF)    {        memset(mmap,0,sizeof(mmap));        if(r==c&&r==k&&k==0)        {            break;        }        int i,j;        for(i=1;i<=r;i++)             scanf("%s",a[i]+1);        chuli();        int t1,t2;        int min=INF;        for(i=1;i<=r;i++)        {            for(j=i;j<=r;j++)            {                for(t1=1,t2=1;t1<=c;t1++)                {                    while(check(i,t1,j,t2)==1&&t2
      
       (j-i+1)*(t2-t1+1))                        min=(j-i+1)*(t2-t1+1);                    }                }            }        }        printf("%d\n",min);    }    return 0;}