题意是这样的（我把题目抽象出来说）
有一个01矩阵，求这个矩阵中最大子矩阵，并且这个子矩阵里仅仅含有1
首先还是进行“悬线”表示，arr[i][j]表示为以(i,j)结尾的最长悬线长度。
用left[j]表示当前行以arr（i,j）为标准长度的最长左拓展长度，right[j]是右拓展长度，显然，当前矩形的大小为arr[i][j]*(right[j]-left[j]+1)
下面就是计算left和right了，这里可以用一维的DP：
1 left[0]=0;
2 for(j=1;j<c;j++)
3 if(arr[i][j-1]>=arr[i][j]) left[j]=left[j-1];
4 else left[j]=j;
5 right[c-1]=c-1;
6 for(j=c-2;j>=0;j--)
7 if(arr[i][j+1]>=arr[i][j]) right[j]=right[j+1];
8 else right[j]=j;
9
完整代码如下：
1 Source Code
2 Problem: 1964 User: yzhw
3 Memory: 4336K Time: 375MS
4 Language: GCC Result: Accepted
5
6 * Source Code
7
8 # include <stdio.h>
9 # define max(a,b) ((a)>(b)?(a):(b))
10 int arr[1005][1005];
11 int right[1005],left[1005];
12 int r,c;
13 int main()
14 {
15 int test,i,j;
16 scanf("%d",&test);
17 while(test--)
18 {
19 scanf("%d%d",&r,&c);
20 int ans=0;
21 for(i=0;i<r;i++)
22 {
23 for(j=0;j<c;j++)
24 {
25 char t[5];
26 scanf("%s",t);
27 arr[i][j]=(*t=='F'?3:0);
28 if(i&&arr[i][j]) arr[i][j]+=arr[i-1][j];
29 }
30 left[0]=0;
31 for(j=1;j<c;j++)
32 if(arr[i][j-1]>=arr[i][j]) left[j]=left[j-1];
33 else left[j]=j;
34 right[c-1]=c-1;
35 for(j=c-2;j>=0;j--)
36 if(arr[i][j+1]>=arr[i][j]) right[j]=right[j+1];
37 else right[j]=j;
38 for(j=0;j<c-1;j++)
39 ans=max(ans,arr[i][j]*(right[j]-left[j]+1));
40 }
41 printf("%d\n",ans);
42 }
43 return 0;
44 }
45
46