题目连接

  • 题意:

    给n*m的0/1矩阵,q次操作,每次有两种:1)将x,y位置值翻转 2)计算以(x,y)为边界的矩形的面积最大值

    (1 ≤ n, m, q ≤ 1000)
  • 分析:

    考虑以(x,y)为下边界的情况,h=(x,y)上边最多的连续1的个数。那么递减的枚举,对于当前hx,仅仅须要看两側能到达的最远距离,使得h(x,ty)不大于h就可以。之后的枚举得到的两側距离大于等于之前的,所以继续之前的两側距离继续枚举就可以。
const int maxn = 1100;

int n, m, q;
int ipt[maxn][maxn];
int up[maxn][maxn], dwn[maxn][maxn], lft[maxn][maxn], rht[maxn][maxn];
int len[maxn];
void updaterow(int r)
{
FE(j, 1, m)
lft[r][j] = (ipt[r][j] == 1 ? lft[r][j - 1] + 1 : 0);
FED(j, m, 1)
rht[r][j] = (ipt[r][j] == 1 ? rht[r][j + 1] + 1 : 0);
}
void updatecol(int c)
{
FE(i, 1, n)
up[i][c] = (ipt[i][c] == 1 ? up[i - 1][c] + 1 : 0);
FED(i, n, 1)
dwn[i][c] = (ipt[i][c] == 1 ? dwn[i + 1][c] + 1 : 0);
}
int maxarea(int s, int len[], int thes)
{
int l = s, r = s, ret = 0;
FED(i, len[s], 1)
{
while (l >= 1 && len[l] >= i)
l--;
while (r <= thes && len[r] >= i)
r++;
ret = max(ret, i * (r - l - 1));
}
return ret;
} int main()
{
while (~RIII(n, m, q))
{
FE(i, 1, n) FE(j, 1, m)
RI(ipt[i][j]);
FE(i, 1, n)
updaterow(i);
FE(j, 1, m)
updatecol(j);
REP(kase, q)
{
int op, x, y;
RIII(op, x, y);
if (op == 1)
{
ipt[x][y] ^= 1;
updatecol(y);
updaterow(x);
}
else
{
int ans = max(maxarea(y, up[x], m), maxarea(y, dwn[x], m));
FE(i, 1, n)
len[i] = lft[i][y];
ans = max(ans, maxarea(x, len, n));
FE(i, 1, n)
len[i] = rht[i][y];
ans = max(ans, maxarea(x, len, n));
WI(ans);
}
}
}
return 0;
}

最新文章

  1. maven log4g 用法
  2. MariaDB 10.1配置
  3. Android JPush(极光推送)的使用教程
  4. Python 前端之JQuery
  5. elasticseach multi-field的实际用途
  6. 垂直居中,水平居中html例子
  7. UVa 11729 - Commando War
  8. This version of MySQL doesn’t yet support ‘LIMIT &amp; IN/ALL/ANY/SOME 错误解决
  9. HDU5727 Necklace
  10. C++: Why pass-by-value is generally more efficient than pass-by-reference for built-in (i.e., C-like) types
  11. CSS3 弹性盒布局模型(转)
  12. UIKit: UIResponder(转自南峰子博客)
  13. eclipse.ini配置eclipse的启动参数
  14. pair work-Elevator Schedule附加题
  15. 【BZOJ2809】【splay启发式合并】dispatching
  16. hdu 2159
  17. Json对象与Json字符串互转(4种转换方式)(转)
  18. python 二叉树实现带括号的四则运算
  19. sqlserver 拆分
  20. Bootstrap3基础 btn-group-vertical 按钮组(横着、竖着排列)

热门文章

  1. html中的rowspan和colspan
  2. java之jvm学习笔记四(安全管理器)
  3. Android 的独特shell命令
  4. APPCAN学习笔记001---app高速开发AppCan.cn平台概述
  5. OpenCV-Python教程(5、初级滤波内容)
  6. 为何要fork()两次来避免产生僵尸进程?
  7. C# 文件操作(全部) 追加、拷贝、删除、移动文件、创建目录 修改文件名、文件夹名
  8. hdu4553(线段树)
  9. Hdu 4539 【状态DP】.cpp
  10. 数学之路-python计算实战(19)-机器视觉-卷积滤波