与第一篇题解的思路一样,但是他是用当前状态推未来状态,我用的用过去状态推当前状态。
其他讨论也有类似与这种问题,但是有人说卡精度。实际上并不是,我将第一片题解复制下来输出了lines,跟我的代码的lines进行比较,完全一样,说明只能是DP过程出错。但是不知道错哪里了。
for(int i=1;i<(1<<n);i++)
for(int j=1;j<=n;j++)
if((i&(1<<j-1)))
{
for(int k=j+1;k<=n;k++)
{
if((!line[j][k])) continue;
if((i|line[j][k])==i)
f[i]=min(f[i],f[(i^line[j][k])]+1);
}
f[i]=min(f[i],f[(i^(1<<j-1))]+1);
break;
}
其实本质都是一样的,我认为我的代码(以及其他推当前状态的人的代码)都是没有问题的,但不知道为什么会错误,麻烦神仙解决一下。