行状态枚举顺序为什么会出错
查看原帖
行状态枚举顺序为什么会出错
23248
izzxm楼主2022/12/31 16:11
//按 i - 1 行、 i 行、 i - 2 行顺序枚举答案正确
for(register int i=2;i<n;i++)
		for(register int j=0;j<up;j++){
			if(j&a[i-1]||(j&(j<<1))||(j&(j<<2)))continue;
			for(register int k=0;k<up;k++){
				if(k&a[i]||j&k||(k&(k<<1))||(k&(k<<2)))continue;
				for(register int l=0;l<up;l++){
					if(l&j||l&k||l&a[i-2]||(l&(l<<1))||(l&(l<<2)))continue;
					f[j][k][i%3]=max(f[j][k][i%3],f[l][j][(i-1)%3]+s[k]);
				}
			}
		}
//按 i 行、 i - 1 行、 i - 2 行顺序枚举答案错误50分
for(register int i=2;i<n;i++)
		for(register int j=0;j<up;j++){
			if(j&(j<<1)||j&(j<<2)||j&a[i])continue;
			for(register int k=0;k<up;k++){
				if(k&(k<<1)||k&(k<<2)||k&a[i-1]||j&k)continue;
				for(register int l=0;l<up;l++){
					if(l&(l<<1)||l&(l<<2)||l&a[i-2]||l&j||l&k)continue;
					f[k][j][i%2]=max(f[k][j][i%2],f[l][k][(i-1)%2]+s[j]);
				}
			}
		}
任何顺序枚举总次数和发生转移的条件应该都是一样的啊,为什么会出现错误。
2022/12/31 16:11
加载中...