学步园

http://www.cnblogs.com/iwtwiioi/p/3885972.html

看到此题我想到用前缀和维护点ij向左和向上能拓展的最大长度，然后设状态f(i, j, 0)表示ij这个点为最大矩形的右下角时的长（横的），f(i, j, 1)表示ij这个店为最大矩形右下角时的宽（竖的），然后决策就是取点(i-1, j-1)的f值拓展一层为ij的，找到一个可行最大解。

过了几个样例我以为就能过了0.0没有认真考虑，，所以造成了前面2个wa。。原因很简单，此方程不满足最优子结构，因为你在拓展最大矩形的时候，不能保证(i+1, j+1)用到自己使得矩形增大，比如

0 0 0 1 1 0

1 1 1 1 1 0

0 0 0 1 1 0

当到点3,5的时候（下标从1开始），用到的是2,4，而2,4的最优解是向左拓展到2,1，因此方程转移后得到的是一个面积为4的矩形，与最优面积为6的矩形相悖，所以这样设是错误的。

看了题解。。。嗯。。我这个方法其实是能用的，只不过换了一点和换了方程。

我们设l[x][y]表示xy这个点向左能拓展到的最远的下标再-1，r[x][y]表示xy这个点想右能拓展到的最远的位置再+1，根据矩形面积低×高，我们只需要将高算出来，找到一个恰当的底，那么面积就求出来了。

首先我们还得维护2个数组，L[x][y]表示xy所构成的最大矩形的底的最左边的点的位置，R[x][y]表示底最右边的点的位置。接下来就是转移了～

l和r很好求，现在我们要求的是L和R，xy的最大面积=(R[x][y]-L[x][y]+1)×高，高可以通过转移时一步步获得，R[x][y]=min(r[x][y]-1, R[x-1][y])，L[x][y]=max(l[x][y]+1, L[x-1][y])，这里取max和min应该很好理解，嗯～此步骤就能看出我之前做法的不足了～这样做是同方向的，所以底是最优的，而高显然是最优的，所以矩形面积显然是最优的。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=a;i>=n;--i)
#define for4(i,a,n) for(i=a;i>n;--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read(a) scanf("%d", &a)
#define print(a) printf("%d", a)
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
 
const int N=1005;
int imap[N][N], l[N][N], r[N][N], L[N][N], R[N][N], h[N][N];
 
int main() {
    int n, m, c, ans=0;
    n=getnum(); m=getnum();
    int i, j, t;
    for1(i, 1, n) for1(j, 1, m) {
        for(c=getchar(); c!='R' && c!='F'; c=getchar());
        if(c=='F') imap[i][j]=1;
    }
    for1(i, 1, n) {
        t=0;
        for1(j, 1, m)
            if(imap[i][j]) l[i][j]=t;
            else L[i][j]=0, t=j;
        t=m+1;
        for3(j, m, 1)
            if(imap[i][j]) r[i][j]=t;
            else R[i][j]=m+1, t=j;
    }
    for1(j, 0, m+1) R[0][j]=m+1;
    for1(i, 1, n) for1(j, 1, m)
        if(imap[i][j]) {
            h[i][j]=h[i-1][j]+1;
            L[i][j]=max(l[i][j]+1, L[i-1][j]);
            R[i][j]=min(r[i][j]-1, R[i-1][j]);
            ans=max((R[i][j]-L[i][j]+1)*h[i][j], ans);
        }
    print(ans*3);
    return 0;
}

然后是单调栈的做法，假设只有i为底的一个点的高比i+!为底的一个点的高，那么i所在的底只有长度为1，而i+1所在底的长度为2，满足单调性，即高度越高，比他矮的都能够len+1，所以可以用单调栈实现。

（看了hzwer神犇的题解后才懂的）

我们维护a[i][j]表示ij点向上拓展的最长长度，那么在i这一条底上，我们将所有的高进行单调栈处理，然后更新ans即可。（图都不用存了）

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=a;i>=n;--i)
#define for4(i,a,n) for(i=a;i>n;--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read(a) scanf("%d", &a)
#define print(a) printf("%d", a)
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
 
const int N=1005;
int n, m, sum[N][N], s[N], l[N], ans, top;
 
void update(int h[]) {
    int len;
    top=0; l[top]=s[top]=0;
    for(int i=1; i<=m; ++i) {
        if(h[i]>=s[top]) s[++top]=h[i], l[top]=1;
        else {
            len=0;
            while(top && s[top]>h[i]) {
                len+=l[top];
                ans=max(ans, s[top]*len);
                top--;
            }
            s[++top]=h[i]; l[top]=len+1;
        }
    }
    len=0;
    while(top) {
        len+=l[top];
        ans=max(ans, s[top]*len);
        top--;
    }
}
 
int main() {
    int c;
    n=getnum(); m=getnum();
    int i, j;
    for1(i, 1, n) for1(j, 1, m) {
        for(c=getchar(); c!='R' && c!='F'; c=getchar());
        if(c=='F') sum[i][j]=sum[i-1][j]+1;
    }
    for1(i, 1, n) update(sum[i]);
    print(ans*3);
    return 0;
}

Description

Input

Output

Sample Input

Sample Output

HINT

Source

By:iwtwiioi 博客地址：http://www.cnblogs.com/iwtwiioi