[luoguP2219] [HAOI2007]修筑绿化带（单调队列）

传送门

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

可以预处理出来

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

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

那么我们可以单调队列跑出来在AC1,BD1的矩阵中的b[i][j]的最小值

枚举i,j，用取a[i][j]ans[i1][j1]的最大值

#include <cstdio>#include <iostream>#define N 2001using 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()inline void work1(int k)}inline void work2(int k)}int main()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;}

上一篇：[luoguP1053] 篝火晚会（贪心 + 乱搞）

下一篇：[luoguP2221] [HAOI2012]高速公路（线段树）