悬线法模板求看
  • 板块P4147 玉蟾宫
  • 楼主Sellaris
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/1/15 23:53
  • 上次更新2023/10/28 12:16:14
查看原帖
悬线法模板求看
567739
Sellaris楼主2022/1/15 23:53

实在不知道哪里戳了。求大佬看。QWQ

///*****Sellaris*****///
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
const int maxn =2022; 
using namespace std;
inline int read(){ int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') { f=-1;} ch=getchar();}
    while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
	return x*f;}//等价于  x=x*10+ch-'0',ch=getchar();
void write(int x){
    if(x<0) { putchar('-'),x=-x;}
    if(x>9) { write(x/10);} putchar(x%10+'0');
	return;}
int ma[maxn][maxn];
int l[maxn][maxn];
int r[maxn][maxn];
int up[maxn][maxn];
inline int max(int x,int y){
	return x>y?x:y;
}
inline int min(int x,int y){
	return x<y?x:y;
}
signed main(){
    int n,m,ans=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char tmp;
            tmp=getchar();
            if(tmp=='F')
                ma[i][j]=1;
            //cin
        }
    }
    for(int i=0;i<=n;i++){
       for(int j=0;j<=m;j++){
        
            l[i][j]=j;
            r[i][j]=j;
            up[i][j]=1;
       }
    }//预处理
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(ma[i][j]==1 && ma[i][j]==ma[i][j-1]){
                l[i][j]=l[i][j-1];
            }
        }//l
        for(int j=m-1;j>=1;j--){
            if(ma[i][j]==1 && ma[i][j]==ma[i][j+1]){
                r[i][j]=r[i][j+1];
            }
        }
    }//r
    int ans1=0,ans2=0;////
    int len;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            //if(i==1 || j==1 ) continue;
            if(ma[i][j]==ma[i-1][j] && ma[i][j]==1){   
                up[i][j]=up[i-1][j]+1;
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
            }
            len=r[i][j]-l[i][j]+1;
            ans=max(ans,up[i][j]*len);
        }
    }//ans
    write(3*ans);
    puts("");
    return 0;
}
2022/1/15 23:53
加载中...