动态规划——悬线法

P4147 玉蟾宫

 1 //动态规划——悬线法
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 const int N=1010;
 6 int n,m;
 7 char a[N][N];
 8 int h[N][N];//保存高度
 9 int l[N][N],r[N][N];
10 int main() {
11     cin>>n>>m;
12     for(int i=1; i<=n; i++) {
13         for(int j=1; j<=m; j++) {
14             cin>>a[i][j];
15             if(a[i][j]=='F') h[i][j]=1;
16             l[i][j]=r[i][j]=j;
17         }
18     }
19     for(int i=1; i<=n; i++) {
20         for(int j=2; j<=m; j++) {//处理本行关系
21             if(a[i][j]=='F'&&a[i][j-1]=='F') l[i][j]=l[i][j-1];
22         }
23         for(int j=m-1; j>=1; j--) {
24             if(a[i][j]=='F'&&a[i][j+1]=='F') r[i][j]=r[i][j+1];
25         }
26     }
27     int ans=0;
28     for(int i=1; i<=n; i++) {
29         for(int j=1; j<=m; j++) {
30             if(a[i][j]=='F'&&a[i-1][j]=='F')  {
31                 h[i][j]=h[i-1][j]+1;
32                 l[i][j]=max(l[i][j],l[i-1][j]);
33                 r[i][j]=min(r[i][j],r[i-1][j]);
34             }
35             if(a[i][j]=='F') ans=max(ans,h[i][j]*(r[i][j]-l[i][j]+1));
36         }
37     }
38     cout<<ans*3;
39     return 0;
40 }