Uva 10074【递推dp】

UVa 10074

题意:求01矩阵的最大子0矩阵。

http://www.csie.ntnu.edu.tw/~u91029/MaximumSubarray.html#2

这里说的很清楚。先求Largest Empty Interval,枚举每个点为矩形的右下角。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 107;
int Map[MAXN][MAXN], width[MAXN][MAXN];
int row, col;

int main()
{
    while (cin>>row>>col&&!(row==0&&col==0))
    {
        int ans = 0;
        for(int i=1;i<=row;i++)
            for (int j = 1; j <= col; j++) {
                cin >> Map[i][j];
                if (Map[i][j]) width[i][j] = 0;
                else width[i][j] = width[i][j - 1] + 1;
            }
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++) {
                int w = 1e9;
                for (int h = 1; i - h + 1 > 0; h++) {
                    if (Map[i][j]) break;
                    w = min(w, width[i - h + 1][j]);
                    ans = max(ans, w*h);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

按照下一个更高效的算法写，不知道为什么会WA，可能是哪里有问题。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 107;
int Map[MAXN][MAXN];
int wl[MAXN], wr[MAXN];
int h[MAXN], l[MAXN], r[MAXN];
int row, col;

int main()
{
    while (scanf("%d%d", &row, &col) == 2, !(row == 0 && col == 0))
    {
        int ans = 0;
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                scanf("%d", &Map[i][j]);
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; j++)
                if (Map[i][j]) wl[j] = 0;
            else wl[j] = wl[j - 1] + 1;
            
            for (int j = col; j >= 1; j--)
                if (Map[i][j]) wr[j] = 0;
            else wr[j] = wr[j + 1] + 1;
    
            for (int j = 1; j <= row; j++)
                if (Map[i][j]) h[j] = 0;
            else h[j] = h[j] + 1;
            
            for (int j = 1; j <= col; j++)
                if (r[j] == 0) r[j] = wr[j];
            else r[j] = min(wr[j], r[j]);
            
            for (int j = 1; j <= col; j++)
                if (l[j] == 0) l[j] = wl[j];
            else l[j] = min(wl[j], l[j]);
            
            for (int j = 1; j <= col; j++)
                        ans = max(ans, (l[j] + r[j] - 1)*h[j]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

最高效的按照栈那种方式写也是WA。。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int MAXN = 107;
int a[MAXN][MAXN], h[MAXN][MAXN];
int col, row;

int main()
{
    while (cin >> row >> col)
    {
        if (!col && !row) break;
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                cin >> a[i][j];
        memset(h, 0, sizeof(h));
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                if (a[i][j]) h[i][j] = 0;
                else h[i][j] = h[i - 1][j] + 1;

                stack<int> st;
                int area;
                int mx = 0;
                for (int i = 1; i <= row; i++)
                {
                    int j;
                    for (j = 1; j <= col;) {
                        if (st.empty() || h[i][st.top()] <= h[i][j])
                            st.push(j++);
                        else {
                            int top = st.top();
                            st.pop();
                            if (st.empty())
                                area = h[i][top] * j;
                            else
                                area = h[i][top] * (j - st.top() - 1);
                            mx = max(mx, area);
                        }
                    }
                    while (!st.empty())
                    {
                        int top = st.top();
                        st.pop();
                        if (st.empty()) area = h[i][top] * j;
                        else
                            area = h[i][top] * (j - st.top() - 1);
                        mx = max(mx, area);
                    }
                }
                cout << mx << endl;
    }
    return 0;
}