杭州seo网站推广排名,上市公司的信息网站,个人网站建设的步骤过程,代做动画毕业设计的网站很好的单调队列题。 题目传送门
题目意思#xff1a;
给定一个 n m n\times m nm 的矩阵#xff0c;求出所有大小为 a b a\times b ab 的子矩形中的最小值的和。 思路#xff1a;
通过题目给的要求建立二维数组 h h h。通过单调队列一行一行地扫#xff0c;将扫出来…很好的单调队列题。 题目传送门
题目意思
给定一个 n × m n\times m n×m 的矩阵求出所有大小为 a × b a\times b a×b 的子矩形中的最小值的和。 思路
通过题目给的要求建立二维数组 h h h。通过单调队列一行一行地扫将扫出来地一个新的数组另存。再通过单调队列一列一列扫这一次一边扫一遍求出 a n s ans ans 的值。最后输出即可。 代码
#include bits/stdc.h
using namespace std;
#define int long long
const int N9e610;
int n,m,a,b;
int x,y,z;
int g[N];
int h[3005][3005];
int hh[3005][3005];
int ans;
signed main()
{cinnmabg[0]xyz;for(int i1;iN;i)g[i](g[i-1]*xy)%z;for(int i1;in;i)//建造高度数组for(int j1;jm;j)h[i][j]g[(i-1)*mj-1];for(int i1;in;i)//扫行{dequeintq;//双端队列for(int j1;jm;j){//如果超出窗口的范围了就出队while(!q.empty()q.front()j-b)q.pop_front();//如果高度搞过枚举的高度出队while(!q.empty()h[i][q.back()]h[i][j])q.pop_back();q.push_back(j);hh[i][j]h[i][q.front()];//用新建的数组保存新的值}}for(int j1;jm;j)//扫列{dequeintq;for(int i1;in;i){//超出范围就出队while(!q.empty()q.front()i-a)q.pop_front();//不符合要求就出队while(!q.empty()hh[q.back()][j]hh[i][j])q.pop_back();q.push_back(i);if(iajb)//保存答案anshh[q.front()][j];}}coutans;return 0;
}完美撒花~
