传送门

需要n*m的算法,考虑单调队列

可以预处理出来

a[i][j]表示以i,j为右下角的绿化带+花坛的和

b[i][j]表示以i,j为右下角的花坛的和

那么我们可以单调队列跑出来在A-C-1,B-D-1的矩阵中的b[i][j]的最小值

枚举i,j,用取a[i][j]-ans[i-1][j-1]的最大值

#include <cstdio>
#include <iostream>
#define N 2001 using namespace std; int n, m, A, B, C, D, E, F, h, t, ans;
int a[N][N], b[N][N], c[N][N], ans1[N][N], ans2[N][N], q[N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void work1(int k)
{
int i;
h = 1, t = 0;
for(i = D; i <= m; i++)
{
while(h <= t && b[k][q[t]] > b[k][i]) t--;
q[++t] = i;
while(h <= t && q[h] <= i - F) h++;
ans1[k][i] = b[k][q[h]];
}
} inline void work2(int k)
{
int i;
h = 1, t = 0;
for(i = C; i <= n; i++)
{
while(h <= t && ans1[q[t]][k] > ans1[i][k]) t--;
q[++t] = i;
while(h <= t && q[h] <= i - E) h++;
ans2[i][k] = ans1[q[h]][k];
}
} int main()
{
int i, j;
n = read();
m = read();
A = read();
B = read();
C = read();
D = read();
E = A - C - 1;
F = B - D - 1;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
c[i][j] = read() + c[i][j - 1] + c[i - 1][j] - c[i - 1][j - 1];
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
if(i >= A && j >= B) a[i][j] = c[i][j] - c[i - A][j] - c[i][j - B] + c[i - A][j - B];
if(i >= C && j >= D) b[i][j] = c[i][j] - c[i - C][j] - c[i][j - D] + c[i - C][j - D];
}
for(i = C; i <= n; i++) work1(i);
for(i = D; i <= m; i++) work2(i);
for(i = A; i <= n; i++)
for(j = B; j <= m; j++)
ans = max(ans, a[i][j] - ans2[i - 1][j - 1]);
printf("%d\n", ans);
return 0;
}

  

最新文章

  1. MySQL/MariaDB/PerconaDB-提权条件竞争漏洞
  2. 【集合框架】JDK1.8源码分析之TreeMap(五)
  3. com.android.build.api.transform.TransformException: com.android.builder.packaging.DuplicateFileException: Duplicate files
  4. Java实现zip压缩多个文件下载
  5. Java读取Execl表格数据
  6. zend 快捷键
  7. jQuery常规选择器
  8. bzoj 2244: [SDOI2011]拦截导弹
  9. NSDictionary、NSMutableDictionary的基本用法
  10. [wikioi]过河卒
  11. careercup-链表 2.6
  12. jQuery Tools:Web开发必备的 jQuery UI 库
  13. My.Ioc 代码示例——谈一谈如何实现装饰器模式,兼谈如何扩展 My.Ioc
  14. If We Were a Child Again
  15. 灵动标签内sql语句调用
  16. WebRTC–getUserMedia-filter
  17. RESTful API接口文档规范小坑
  18. 使用virtualenvwrapper模块管理python虚拟环境
  19. Linux TOP命令按内存占用排序和按CPU占用排序
  20. Shell脚本中的 测试开关 和 特殊参数

热门文章

  1. Oracle汇总
  2. linux 删除文件后空间没有释放的解决办法
  3. vijos 1448 校门外的树 (不是05年普及组那题)
  4. codevs 4165 ​高精度求阶乘
  5. shiro 配置拦截规则之后css和js等失效
  6. 如何在Ubuntu 16.04上安装Apache Web服务器
  7. JavaScript中对象的属性:如何遍历属性
  8. 二分查找算法java
  9. ios retain copy 以及copy协议
  10. 欧拉函数φ(x)简要介绍及c++实现