[luoguP1169] [ZJOI2007]棋盘制作(单调栈)
2024-09-03 03:23:41
和玉蟾宫差不多
——代码
#include <cstdio>
#include <iostream> using namespace std; const int MAXN = ;
int n, m, ans1, ans2, top;
int a[MAXN][MAXN][], s[MAXN], r[MAXN], l[MAXN]; inline void work(int k)
{
int i, j;
for(i = ; i <= ; i++)
{
a[k][][i] = a[k][m + ][i] = -;
top = ;
for(j = ; j <= m + ; j++)
{
while(top && a[k][s[top]][i] > a[k][j][i]) r[s[top--]] = j;
s[++top] = j;
}
top = ;
for(j = m; j >= ; j--)
{
while(top && a[k][s[top]][i] > a[k][j][i]) l[s[top--]] = j;
s[++top] = j;
}
for(j = ; j <= m; j++)
{
ans1 = max(ans1, min(a[k][j][i], r[j] - l[j] - ) * min(a[k][j][i], r[j] - l[j] - ));
ans2 = max(ans2, a[k][j][i] * (r[j] - l[j] - ));
}
}
} int main()
{
int i, j, x;
scanf("%d %d", &n, &m);
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
{
scanf("%d", &x);
if((i + j) % ) x ^= ;
a[i][j][x] = a[i - ][j][x] + ;
}
for(i = ; i <= n; i++) work(i);
printf("%d\n%d\n", ans1, ans2);
return ;
}
最新文章
- mssql 2008 游标 临时表 作业批处理失败问题
- The differences between Java application and Java applet
- C++ sstream 中处理字符串
- Codeforces Round #FF (Div. 1) A. DZY Loves Sequences
- Java流操作之转换流
- Erlang虚拟机的启动
- 基于Verilog HDL 的数字电压表设计
- 用$.getJSON() 和$.post()获取第三方数据做页面 ——惠品折页面(1)
- 手写JAVA虚拟机(二)——实现java命令行
- HTML5 新增的 input 事件
- 微信小程序的桌面图标问题
- WPF Chart
- 14. Longest Common Prefix(暴力循环)
- Spring容器中bean的生命周期以及关注spring bean对象的后置处理器:BeanPostProcessor(一个接口)
- javascript中个别方法注意事项
- ActiveMQ笔记之点对点队列(Point-to-Point)
- Python中from module import *语法
- 批处理命令中set定义的两种变量介绍 计算机基础知识
- pat1013. Battle Over Cities (25)
- Windows Service的转换与部署