社区讨论
关于只有第一个点挂掉
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 条回复,欢迎继续交流。
正在加载回复...