題意是這樣的（我把題目抽象出來(lái)說(shuō)）
有一個(gè)01矩陣，求這個(gè)矩陣中最大子矩陣，并且這個(gè)子矩陣?yán)飪H僅含有1
首先還是進(jìn)行“懸線”表示，arr[i][j]表示為以(i,j)結(jié)尾的最長(zhǎng)懸線長(zhǎng)度。
用left[j]表示當(dāng)前行以arr（i,j）為標(biāo)準(zhǔn)長(zhǎng)度的最長(zhǎng)左拓展長(zhǎng)度，right[j]是右拓展長(zhǎng)度，顯然，當(dāng)前矩形的大小為arr[i][j]*(right[j]-left[j]+1)
下面就是計(jì)算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