首页 > 代码库 > poj - 1156 - A STRIP OF LAND(枚举 + 单调队列 + 输入开挂)
poj - 1156 - A STRIP OF LAND(枚举 + 单调队列 + 输入开挂)
题意:一个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; }
poj - 1156 - A STRIP OF LAND(枚举 + 单调队列 + 输入开挂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。