CF480E Parking Lot（单调队列+dp然鹅并不是优化）

（全英文题面所以直接放化简题意）

题意：在一个二维平面内，初始有一些点，然后每个时间点加入一些点，对每个时间点求平面内最大的无障碍正方形

（这次的题目是真的神仙啊。。。）

首先，考虑暴力，如果对每一个加点进行一遍扫描，那么，可以跑到天荒地老了。。。
其次，如果像以前的dp一样跑呢？因为是动态的，所以不行。。。
很容易想到，这个面积一定是单调不增的，于是，就可以倒序来，变成加点，离线做。
那么，有了加点就可以跑暴力了吗？很显然不行。。。
那怎么办呢？

solution：

（以下初始思路来自老师）

这个正方形可能出现在哪里？

一个点左上
左下
右上
右下

一个正方形由长和宽构成，要找最大边长，其实就是要维护两个东西：长和宽。

分别考虑长宽如何维护（好吧差不多都是边长）

宽：它可能经过一个点，也就是这个点在宽这条边上。

于是不太容易想到：维护两个dp数组，存每个点向左右能拓展的长度。

但是，如果依旧暴力更新，还是会炸成渣滓。。。

瞪大眼看题，当一个点更新时，只有它所在的一行会变，所以就可以O（n）更新dp数组了。

于是，只要在每个点加上后更新dp数组，然后查出最大正方形，就完事了

下面考虑列：

能不能像刚刚那样继续dp嘞？（像cdq那样dp套dp呢？？？）如果这样做，那可能会得到一个错位的正方形。。。很麻烦.....

况且我们要去最大的不是吗？这好像有什么提示.....

想想我学过的维护最值的数据结构（qsort rmq 线段树单调队列主席树平衡树树套树）

再结合一下问题实际：找长度，不太容易想到，对于每一个答案，进行一次check。这个check，有点像二分，对于每一个可行答案进行判断然后更新最优解。而这个可行答案，就是看是否能找到更大的正方形。

对此，只需要枚举是否能找到比当前更大的边长就行了。因为它是正方形，所以长宽相等，这里列问题就转化为了：

对于每一个定长区间，找最大的一个之前处理出的dp数组里是否有一个长度大于等于它的值，也就是最大值。

这就很明朗了，线段树，单调队列。

两者差距在哪里呢？线段树O（nlogn）单调队列O（n）；

我用了单调队列。

这份代码给我的感觉就是：代码还可以继续化简，逻辑运算符可以有效增加效率和增加美观度

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

char s[maxn];

int n,m,k;

int a[maxn][maxn];

struct node

{

    int x,y,res;

}ans[maxn];

int f[maxn][maxn];

int l[maxn][maxn];

int r[maxn][maxn];

void init()

{

    scanf("%d%d%d",&n,&m,&k);

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

    {

        scanf("%s",s+);

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

        {

            a[i][j]=(s[j]=='.');

        }

    }

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

    {

        scanf("%d%d",&ans[i].x,&ans[i].y);

        a[ans[i].x][ans[i].y]=;

    }

}

void dp()

{

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

    {

        for(int j=m;j>=;j--)

        {

            if(!a[i][j])

            continue;

            if(i==||j==m)

            {

                f[i][j]=;

                ans[k].res=max(ans[k].res,);

                continue;

            }

            f[i][j]=min(f[i-][j],f[i][j+]);

            if(a[i-f[i][j]][j+f[i][j]])f[i][j]++;

            ans[k].res=max(ans[k].res,f[i][j]);

        }

    }

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

    {

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

        {

            l[i][j]=a[i][j]*(l[i][j-]+);

        }

    }

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

    {

        for(int j=m;j>=;j--)

        {

            r[i][j]=a[i][j]*(r[i][j+]+);

        }

    }

}

int tmp[maxn];

int q[maxn];

bool check(int x,int y)

{

    int head=,tail=;

    memset(tmp,,sizeof(tmp));

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

    {

        while(head<=tail&&l[q[tail]][y]>=l[i][y])

        tail--;

        q[++tail]=i;

        while(q[head]<=i-x)

        head++;

        tmp[i]+=l[q[head]][y];

    }

    head=;tail=;

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

    {

        while(head<=tail&&r[q[tail]][y]>=r[i][y])

        tail--;

        q[++tail]=i;

        while(q[head]<=i-x)

        head++;

        tmp[i]+=r[q[head]][y]-;

    }

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

    {

        if(tmp[i]>=x)

        return ;

    }

    return ;

}

void solve()

{

    int tem=ans[k].res;

    for(int i=k;i>=;i--)

    {

        ans[i].res=tem;

        int x=ans[i].x;

        int y=ans[i].y;

        a[x][y]=;

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

        {

            l[x][j]=a[x][j]*(l[x][j-]+);

        }

        for(int j=m;j>=;j--)

        {

            r[x][j]=a[x][j]*(r[x][j+]+);

        }

        while(check(tem+,y))

        tem++;

    }

    ans[].res=tem;

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

    {

        printf("%d\n",ans[i].res);

    }

}

int main()

{

    init();

    dp();

    solve();

    return ;

}

（完）

巴特西

CF480E Parking Lot（单调队列+dp然鹅并不是优化）

最新文章

热门文章