悬线法求调
  • 板块UVA1330 City Game
  • 楼主hjqhs
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/1 12:09
  • 上次更新2023/11/2 16:48:47
查看原帖
悬线法求调
724988
hjqhs楼主2023/10/1 12:09

已过 P4147 和样例 但是在这里 WA

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int INF=0x3f3f3f3f;
int T,n,m,ans=-INF;
char a[MAXN][MAXN];
int h[MAXN][MAXN],l[MAXN][MAXN],r[MAXN][MAXN];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
  cin>>T;
  while(T--){
    n=m=0,memset(a,0,sizeof(a)),memset(h,0,sizeof(h)),memset(l,0,sizeof(l)),memset(r,0,sizeof(r)),ans=-INF;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        cin>>a[i][j];
        h[i][j]=1;r[i][j]=l[i][j]=j;
      }
    }
    for(int i=1;i<=n;++i){
      for(int j=2;j<=m;++j){
        if(a[i][j]=='F'&&a[i][j-1]=='F'){
          l[i][j]=l[i][j-1];
        }
      }
    }
    for(int i=1;i<=n;++i){
      for(int j=m-1;j>=1;--j){
        if(a[i][j]=='F'&&a[i][j+1]=='F'){
          r[i][j]=r[i][j+1];
        }
      }
    }
    for(int i=2;i<=n;++i){
      for(int j=1;j<=m;++j){
        if(a[i][j]=='F'&&a[i-1][j]=='F'){
          h[i][j]=h[i-1][j]+1;
        }
      }
    }
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        if(i>1&&a[i][j]=='F'&&a[i-1][j]=='F'){
          l[i][j]=max(l[i][j],l[i-1][j]);
          r[i][j]=min(r[i][j],r[i-1][j]);
        }
        if(a[i][j]=='F')ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
      }
    }
    if(ans==-INF){cout<<0<<'\n';return 0;}
    else{cout<<3*ans<<'\n';}
  }
	return 0;
}

@p_Hydroxy

2023/10/1 12:09
加载中...