欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.08.17 洛谷P3135 [USACO16JAN]堡哞(前缀和处理)

程序员文章站 2022-05-12 23:32:09
...

传送门
有趣的前缀和。
数据范围中的n200提示我需要写出来一个O(n3)的算法,思来想去感觉前缀和挺靠谱的于是写了写发现只有84,检查后发现把m打成了n(造数据的真善良。。。)。
所以说这道题怎么用前缀和呢?
我们先用O(n)的时间枚举矩形的竖直的那条边的长度,然后O(n)选取矩形的左上角点(默认都从最左边一列开始,在右边开始的情况会在跳双指针的时候纳入统计范围),最后上一波双指针就行了。
这题之所以能用双指针将O(n2)优化成O(n)是因为这个东西具有单调性,也就是矩形的左竖直边能选左做的就尽量选靠左的,否则不优。

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[205][205],sum[205][205],b[205],ans=0;
char s[205];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%s",s+1);
        for(int j=1;j<=m;++j){
            sum[i][j]=sum[i-1][j];
            if(s[j]=='.')a[i][j]=1,++sum[i][j];
        }
    }
    for(int len=1;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            for(int j=1;j<=m;++j)b[j]=sum[i+len-1][j]-sum[i-1][j];
            for(int l=1,r=1;;){
                while((!a[i][l]||!a[i+len-1][l]||b[l]!=len)&&l<=m)++l;
                r=l;
                if(l>m)break;
                while(a[i][r]&&a[i+len-1][r]&&r<=m){
                    if(b[r]==len)ans=max(ans,(r-l+1)*len);
                    ++r;
                }
                if(r>m)break;
                l=r+1;
            }
        }
    }
    cout<<ans;
    return 0;
}
相关标签: 好题