MnZn刚学状压dp,求助大佬
查看原帖
MnZn刚学状压dp,求助大佬
261262
WaltVBAlston楼主2021/11/21 21:24

RT,这是一篇题解的一部分code:

	for(k=1;k<(1<<N);k++)//枚举所有二进制的状态 
	{
		for(i=1;i<=N;i++)
		{
			if((k&(1<<(i-1)))==0)
				continue;//i的位置没被走过,所以不需要再继续计算了 
			for(j=1;j<=N;j++)
			{
				if(i==j)
					continue;//同一个点不需要再计算 
				if((k&(1<<(j-1)))==0)
					continue;//j的位置没走过  
				F[i][k]=min(F[i][k],F[j][k-(1<<(i-1))]+a[i][j]);
			} 
		} 
	} 

最不理解的是这一块:

				if((k&(1<<(j-1)))==0)
					continue;//j的位置没走过  

难道不应该是j没走过才需要加入吗,j走过了说明已经包含在路径中了啊,那不就说明已经更新过了吗? 我不理解

其他小问题:

我能不能最外层枚举i,中间枚举k,最里面枚举j?

2021/11/21 21:24
加载中...