题目传送门
在上一道扫描线裸题，这道题还需要DP,但是其实DP的过程就是在做扫描线的过程。在DP的时候就可知道当前位置的四周情况，并把信息合并在一些具有全局性质的数组中，这就很类似于扫描线了。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define INF 2100000000 #define ll long long #define clr(x) memset(x,0,sizeof(x)) using namespace std; const int maxn = 1e3+20; int mp[maxn][maxn],_up[maxn][maxn],_left[maxn][maxn],_right[maxn][maxn]; int Ti,m,n,ans,ch; int main(){ scanf("%d",&Ti); while(Ti--){ scanf("%d%d",&m,&n),ans=0; for(int i=0;i<m;i++) for(int j=0;j<n;j++){ while((ch=getchar())!='F'&&ch!='R'); mp[i][j]=ch=='F'?0:1; } for(int i=0;i<m;i++){ int lc=-1,rc=n; for(int j=0;j<n;j++){ if(mp[i][j]==1)_up[i][j]=_left[i][j]=0,lc=j; else{ _up[i][j]=i==0?1:_up[i-1][j]+1; _left[i][j]=i==0?lc+1:max(_left[i-1][j],lc+1); } } for(int j=n-1;j>=0;j--){ if(mp[i][j]==1)_right[i][j]=n,rc=j; else{ _right[i][j]=i==0?rc-1:min(_right[i-1][j],rc-1); ans=max(ans,_up[i][j]*(_right[i][j]-_left[i][j]+1)); } } } cout<<ans*3<<endl; } return 0; }依我看，扫描线的核心思想就是我所写的高山算法的更广泛的运用。。。
