40 分蒟蒻求助
查看原帖
40 分蒟蒻求助
1251949
STDLRZ楼主2024/3/28 07:41
/*

   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+1<<" "<<j-d+1<<" "<<a<<" "<<b<<" "<<sum(i-c+1,j-d+1,a,b)<<" "<<z[qq.front()][q[qq.front()].front()]<<"\n";
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}
2024/3/28 07:41
加载中...