题意：一个V * U的矩阵，每个元素有一个高度Hxy，问长不超过100，且最高值与最低值的差不超过C的子矩阵的最大面积(1 <= U <= 700, 1 <= V <= 700, -30,000 <= Hxy <= 30,000, 0 <= C <= 10 )。
题目链接：http://poj.org/problem?id=1156
——>>枚举子矩阵的左右宽度（保证枚举宽度不超过100，同时记录所枚举左右区间的每行的最大最小值），再枚举子矩阵的上下宽度（用单调队列优化判C）。
#include <cstdio>
#include <algorithm>
#include <cstring>using std::min;
using std::max;const int MAXN = 700 + 1;int H[MAXN][MAXN];
int arrRowMin[MAXN];
int arrRowMax[MAXN];struct DQ
{int nFront;int nTail;int arr[MAXN];DQ():nFront(0), nTail(0){}void Init(){nFront = nTail = 0;}void PushBackMin(int nId){while (nFront != nTail && arrRowMin[nId] <= arrRowMin[arr[nTail - 1]]){nTail--;}arr[nTail++] = nId;}void PushBackMax(int nId){while (nFront != nTail && arrRowMax[nId] >= arrRowMax[arr[nTail - 1]]){nTail--;}arr[nTail++] = nId;}void PopFront(){nFront++;}int Front(){return arr[nFront];}bool Empty(){return nFront == nTail;}
};int ReadInt()
{int nRet = 0;int nFlag = 1;char chIn;chIn = getchar();if (chIn == '-'){nFlag = -1;}else{nRet = nRet * 10 + chIn - '0';}while ((chIn = getchar()) && chIn >= '0' && chIn <= '9'){nRet = nRet * 10 + chIn - '0';}return nRet * nFlag;
}int main()
{int U, V, C;while (scanf("%d%d%d", &U, &V, &C) == 3){getchar();for (int i = 1; i <= V; ++i){for (int j = 1; j <= U; ++j){H[i][j] = ReadInt();}}DQ dqMin;DQ dqMax;int nRet = 0;for (int nLcol = 1; nLcol <= U; ++nLcol){memset(arrRowMin, 0x3f, sizeof(arrRowMin));memset(arrRowMax, 0xc0, sizeof(arrRowMax));for (int nRcol = nLcol; nRcol <= U && nRcol - nLcol + 1 <= 100; ++nRcol){for (int i = 1; i <= V; ++i){arrRowMin[i] = min(arrRowMin[i], H[i][nRcol]);arrRowMax[i] = max(arrRowMax[i], H[i][nRcol]);}int nWidth = nRcol - nLcol + 1;dqMin.Init();dqMax.Init();for (int i = 1, j = 1; j <= V && nWidth * (V - i + 1) > nRet; ++j){dqMin.PushBackMin(j);dqMax.PushBackMax(j);while (i <= j && !dqMax.Empty() && !dqMin.Empty() && arrRowMax[dqMax.Front()] - arrRowMin[dqMin.Front()] > C){i++;while (!dqMax.Empty() && dqMax.Front() < i){dqMax.PopFront();}while (!dqMin.Empty() && dqMin.Front() < i){dqMin.PopFront();}}nRet = max(nRet, nWidth * (j - i + 1));}}}printf("%d\n", nRet);}return 0;
}