算法题：uva 1330

题目链接:

http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076

以前做过一道一维的，这题只是变成了二维的，其他方法都一样。HDU 1506  Largest Rectangle in a Histogram   题解

代码1：

#include<cstdio>
#include<cstring>
#include<stack>
using std::stack;  

const int MAXN = 1010;
char str[MAXN*3];
int sum[MAXN][MAXN];
int left[MAXN], right[MAXN];
int n, m;  

inline void input(){
    scanf("%d%d%*c", &n, &m);
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            char ch = getchar();
            while(ch!='F' && ch!='R') ch=getchar();
            sum[i][j] = ch=='R'?0:1;
            if(sum[i][j]) sum[i][j] += sum[i-1][j];
        }
    }
}  

inline void solve(){
    input();
    int ans = 0;
    for(int i=1; i<=n; ++i){
        sum[i][0] = sum[i][m+1] = -1;
        for(int j=1; j<=m; ++j)
            left[j]=right[j]=j;
        for(int j=1; j<=m; ++j){
            while(sum[i][j] <= sum[i][left[j]-1])
                left[j] = left[left[j]-1];
        }
        for(int j=m; j>=1; --j){
            while(sum[i][j] <= sum[i][right[j]+1])
                right[j] = right[right[j]+1];
            int tmp = (right[j]-left[j]+1)*sum[i][j];
            if(tmp > ans) ans=tmp;
        }
    }
    printf("%d\n", ans*3);
}  

int main(){
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){  

       solve();
    }
    return 0;
}

代码2（栈扫描）：

#include<cstdio>
#include<cstring>
#include<stack>
using std::stack;  

const int MAXN = 1010;
char str[MAXN*3];
int sum[MAXN][MAXN];
int n, m;  

inline void input(){
    scanf("%d%d%*c", &n, &m);
    memset(sum, 0, sizeof(sum));
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            char ch = getchar();
            while(ch!='F' && ch!='R') ch=getchar();
            sum[i][j] = ch=='R'?0:1;
            if(sum[i][j]) sum[i][j] += sum[i-1][j];
        }
    }
}  

inline void solve(){
    input();
    int ans = 0;
    for(int i=1; i<=n; ++i){
        sum[i][0] = sum[i][m+1] = -1;
        stack<int>q;
        for(int j=1; j<=m+1; ++j){
            if(q.empty() || sum[i][j]>sum[i][q.top()]){
                q.push(j);
            }
            else if(sum[i][j] < sum[i][q.top()]){
                int pos;
                while(!q.empty() && sum[i][q.top()]>sum[i][j]){
                    int tmp = (j-q.top())*sum[i][q.top()];
                    if(tmp > ans)
                        ans = tmp;
                    pos = q.top();
                    q.pop();
                }
                q.push(pos);
                sum[i][pos] = sum[i][j];
            }
        }
    }
    printf("%d\n", ans*3);
}  

int main(){
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){  

       solve();
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， int
， include
， 求助一道算法题
， 算法题
， 一维
二维
133、1330年、韩国1330、1330日元、13306，以便于您获取更多的相关知识。