Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

栈解法代码

Posted by 1007783493 at 2016-08-10 16:57:21 on Problem 3494
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
const int maxn = 2005;

int n,m;
int arr[maxn][maxn],data[maxn][maxn];
int solve(int row){
    stack<int>s;
    int ans = 0;
    s.push(0);
    data[row][0] = 0;
    data[row][m+1] = 0;
    for (int j = 1; j <= m+1; ++j) {
        while (data[row][j] < data[row][s.top()]) {
            int a = data[row][s.top()]; s.pop();
            int b = j - s.top() - 1;
            if (a * b > ans) {
                ans = a * b;
            }
        }
        s.push(j);
    }
    return ans;
}
int main() {

    // RE
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j){
                scanf("%d",&arr[i][j]);
            }
        }
        clr(data,0);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j){
                if(arr[i][j]) data[i][j] = arr[i][j] + data[i-1][j];
                else   data[i][j] = 0;
            }
        }
        int ans =  0;
        for (int i = 1; i <= n; ++i){
            ans = max(ans,solve(i));
        }
        printf("%d\n", ans);
    }
    return 0;
}

夹带私货链接: http://blog.csdn.net/u012469987/article/details/52173473

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator