在此题中,这样是错的:
void DP(int x,int y,int len,int d){
int hh=0,tt=-1;
for(int i=1;;i++,x+=dx[d],y+=dy[d]){
if(x<1||x>n||y<1||y>m) return;
if(s[x][y]=='x'){
hh=0,tt=-1;
continue;
}
while(hh<=tt&&i-q[hh].pos>len) hh++;
//踢出不合法情况
f[x][y]=max(f[x][y],q[hh].ans+i-q[hh].pos);
//更新f[x][y]
while(hh<=tt&&q[tt].ans-q[tt].pos<f[x][y]-i) tt--;
//用更新后的f[x][y]对比踢出不优情况
q[++tt]={f[x][y],i};
//踢出队尾不优情况后将f[x][y]加入队列
ans=max(ans,f[x][y]);
}
}
但这种我认为不对的做法就是对的
void DP(int x,int y,int len,int d){
int hh=0,tt=-1;
for(int i=1;;i++,x+=dx[d],y+=dy[d]){
if(x<1||x>n||y<1||y>m) return;
if(s[x][y]=='x'){
hh=0,tt=-1;
continue;
}
while(hh<=tt&&i-q[hh].pos>len) hh++;
while(hh<=tt&&q[tt].ans-q[tt].pos<f[x][y]-i) tt--;
//这份代码,在没有更新F[x][y]的情况下就踢出了不优情况
q[++tt]={f[x][y],i};
//并且将f[x][y]加入队尾后才更新f[x][y],那么这样的f[x][y]不一定是当前最好情况啊?
f[x][y]=max(f[x][y],q[hh].ans+i-q[hh].pos);
ans=max(ans,f[x][y]);
}
}
感谢您的回答,这对我真的很重要,,,感觉已经忘掉单调队列了,悬赏两个永久不取消的关注