Brief description:

在一个 N*M 的矩阵中寻找一个 A*B 的子矩阵，在这个 A*B 阶的矩阵中再寻找一个 C*D 的子矩阵，
使得这两个矩阵的差最大，另、C*D 子矩阵不可以触碰 A*B 矩阵的边界。
( .. N ≤ 1000 … ）

Analysis:

枚举一阶子矩阵，对二阶子矩阵和每列，分别维护单调队列，时间复杂度 O(NM)。

const int N = 1001;

struct MonoList{
    int a[N], b[N];
    int op, cz, nn;
    inline int size(){
        return op - cz + 1;
    }
    inline int front(){
        return a[cz];
    }
    void init(){
        a[0] = 0, op = -1, cz = 0;
    }
    void init(int l){
        a[0] = 0, op = -1, cz = 0, nn = l;
    }

    void push_without_pop(int val, int label){
        while (op >= cz && val <= a[op]){
            --op;
        }
        a[++op] = val, b[op] = label;
    }

    void push(int val, int label){
        push_without_pop(val, label);
        if (b[cz] + nn == b[op]) ++cz;
    }

} Sub, Col[N];

int _T[101], s[N][N], ans;
int n0, m0, n1, m1, n2, m2;

inline int s1(int x, int y){
    return s[x][y] - s[x-n1][y] - s[x][y-m1] + s[x-n1][y-m1];
}

inline int s2(int x, int y){
    return s[x][y] - s[x-n2][y] - s[x][y-m2] + s[x-n2][y-m2];
}

int main(){

    REP_1(i, 100) _T[i] = (i * 71 + 17) % 100 + 1; Rush{

        RD(n0, m0, n1, m1, n2, m2);

        REP_1(i, n0) {
            int t; RD(t), s[i][1] = s[i-1][1] + t;
            FOR_1(j, 2, m0){
                t = _T[t];
                s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + t;
            }
        }

        ans = 0; FOR(j, m2+1, m0) Col[j].init(n1 - n2 - 1);
        Sub.init(m1 - m2 - 1);

        FOR(i, n2+1, n1-1) FOR(j, m2+1, m0)
        Col[j].push_without_pop(s2(i, j), i);

        FOR_1(i, n1, n0){

            FOR(j, m2+1, m0) Col[j].push(s2(i-1, j), i-1);

            Sub.init(); FOR(j, m2+1, m1) Sub.push_without_pop(Col[j].front(), j);
            FOR(j, m1, m0) {
                checkMax(ans, s1(i, j) - Sub.front());
                Sub.push(Col[j].front(), j);
            }

            checkMax(ans, s1(i, m0) - Sub.front());
        }

        OT(ans);
    }
}

External link:

http://www.spoj.pl/problems/MATRIX2/

Posted by xiaodao
Category: SPOJ
Tags: 单调队列