社区讨论

关于只有第一个点挂掉

P2219[HAOI2007] 修筑绿化带参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locs2ulb
此快照首次捕获于
2023/10/30 18:49
2 年前
此快照最后确认于
2023/11/05 05:33
2 年前
查看原帖
我用的是两个单调队列的解法,求助为什么只有第一个点挂掉过不去了啊QAQ
CPP
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define ll long long
using namespace std;
const ll S=1e3+6;
ll m,n,a,b,c,d,ans=0;
ll c1,c2;
ll x[S][S],fix[S][S],rec[S][S],f1[S][S],f2[S][S];
deque <ll> q;
ll R(ll xx,ll yy){
	return fix[xx+a-1][yy]-fix[xx-1][yy]-fix[xx+a-1][yy-b]+fix[xx-1][yy-b];
}
int main(){
	scanf("%lld%lld%lld%lld%lld%lld",&m,&n,&a,&b,&c,&d);
	c1=a-c-1,c2=b-d-1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&x[i][j]);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			fix[i][j]=fix[i-1][j]+fix[i][j-1]+x[i][j]-fix[i-1][j-1];
			//printf("%lld ",fix[i][j]);
		}
		//printf("\n");
	}	
	for(int i=1;i<=m-c+1;i++){
		while(q.size()){
			q.pop_back();
		}
		for(int j=d;j<=n;j++){
			rec[i][j]=fix[i+c-1][j]-fix[i-1][j]-fix[i+c-1][j-d]+fix[i-1][j-d];
			while(q.size()&&q.front()<j-c2+1){
				q.pop_front();
			}
			while(q.size()&&rec[i][q.front()]>rec[i][j]){
				q.pop_back();
			}
			q.push_back(j);
			f1[i][j]=q.front();
			//printf("[%d,%d %lld %lld]  ",i,j,f1[i][j],rec[i][f1[i][j]]);
		}
		//printf("\n");
	}
	
	for(int i=d;i<=n;i++){
		while(q.size()){
			q.pop_back();
		}
		for(int j=m-c+1;j>=1;j--){
			while(q.size()&&q.front()>j+c1-1){
				q.pop_front();
			}
			while(q.size()&&rec[q.back()][f1[q.back()][i]]>rec[j][f1[j][i]]){
				q.pop_back();
			}
			q.push_back(j);
			f2[j][i]=q.front();
		}
	}
	for(int i=1;i<=m-a+1;i++){
		for(int j=b;j<=n;j++){
			ans=max(ans,R(i,j)-rec[f2[i+1][j-1]][f1[f2[i+1][j-1]][j-1]]);
			//printf("[%d %d %lld] ",i,j,ans);
		}
		//printf("\n");
	}
	printf("%lld\n",ans);
	return 0;
}
//4 5 4 5 1 1
//20 19 18 17 16
//15 14 13 12 11
//10 9 8 7 6
//5 4 3 2 1

回复

2 条回复,欢迎继续交流。

正在加载回复...