能帮我调一下吗?
/*
x x x x x x
x x x x x x
x x x x x x
x x x x x x
现在有一个 4*6 的矩阵
让我们把它给改变一下
首先,我们可以知道 c*d
如 c=2,d=3
所以,可以化成:
S[1] S[2] S[3] S[4]
S[5] S[6] S[7] S[8]
S[9] S[10] S[11] S[12]
这代表我们在求 a*b 的时候,
可以这样:
假设 a=3,b=3
那我们发现,第一次 ( 在坐标 (1,1) 左下角为 (3,3) )
筐住的点是:
S[1]
S[5]
那么也就是可以转换成 ST 表。
为什么?
为什么?
但不过 ST 表会超时。
那我们就可以拿着这个模版,把每一个都提前算出来。
这样,也可以。
来一个复杂一点的情况:
假设 a=3,b=4
则我们发现,他筐住的点是 S[1] S[5] S[2] S[6]
这东西最适合用单调队列解决。
可以同步单调。
则,本题已做完。
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,d;
int A[1010][1010];
int s[1010][1010]; // 最多可能是 1000*1000*100=10^3*10^3*10^2=10^8, 并不会超空间。
int z[1010][1010]; // 经转换得到的矩阵
deque<int> q[1010]; // 亲爱的单调队列
int ans=-2e9; // 答案
int sum(int a,int b,int alen,int blen){ // 以 (a,b) 为左上角,长为 alen,宽为 blen 的总和。
int x=a+alen-1,y=b+blen-1; // 算出右下角
return s[x][y]-s[a-1][y]-s[x][b-1]+s[a-1][b-1]; // 转换矩形第二步 : 算出 如上所述 的总和。
/*
如:(x,y)=(3,3)
(a,b)=(1,2)
则我们覆盖的:
* * *
* * *
* * *
->
* * *
* * *
* * *
->
x * *
x * *
x * *
->
x * *
x * *
x * *
*/
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>a>>b>>c>>d;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) cin>>A[i][j]; // 输入
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+A[i][j]; // 转换矩形第一步 : 算二维前缀和
for(int i=1;i<=n-c+1;++i){ // 转换矩形第三步 : 枚举行坐标
for(int j=1;j<=m-d+1;++j){ // 转换矩形第四步 : 枚举纵坐标
z[i][j]=sum(i,j,c,d); // 转换矩形第五步 : 算出总和
}
}
// 转换矩形已完成,差不知道几个单调队列
// 单调队列的行和列的上限是:
int upi=a-c+1,upj=b-d+1;
for(int j=2;j<=m-d;++j){ // 枚举列
for(int i=2;i<=n-c;++i){ // 枚举行
while(q[i].size() && j-q[i].front()>=upj) q[i].pop_front();
while(q[i].size() && z[i][q[i].back()]>=z[i][j]) q[i].pop_back();
q[i].push_back(j);
}
deque<int> qq;
for(int i=2;i<=n-c;++i){
while(qq.size() && i-qq.front()>=upi) qq.pop_front();
while(qq.size() && z[qq.back()][q[qq.back()].front()]>=z[i][q[i].front()]) qq.pop_back();
qq.push_back(i);
if(j>=upj-1 && i>=upi-1){ // 满足最小条件
ans=max(ans,sum(i-c+1,j-d+1,a,b)-z[qq.front()][q[qq.front()].front()]);
// cout<<i-c<<" "<<j-d<<" "<<a<<" "<<b<<" "<<sum(i-c,j-d,a,b)<<" "<<z[qq.front()][q[qq.front()].front()]<<"\n";
}
}
}
cout<<ans<<"\n";
return 0;
}
蟹蟹泥