关于单调队列优化dp的顺序
查看原帖
关于单调队列优化dp的顺序
315205
Kniqht楼主2023/10/20 06:41

在此题中,这样是错的:

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]);
	} 
}

感谢您的回答,这对我真的很重要,,,感觉已经忘掉单调队列了,悬赏两个永久不取消的关注

2023/10/20 06:41
加载中...