KOI打击过以后决定小做做最简单的 基于连通性的状态压缩动态规划。

Cdq神牛的论文看了很久~ 还是找了某代码看~ 果然我理解代码的能力还是稍微比看solution好点。

那是一道Betsy's Tour. Code是逐格递推，每个格子滚动数组：

 int main{int i,j,k; int nx,t1,t2,u,v; int size=1<<(m+1)*2; memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); f1[0]-->        int i,j,k;
        int nx,t1,t2,u,v;
        int size=1<<(m+1)*2;
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        f1[0]=1;
        _f1=f1;    _f2=f2;
        for (i=0;i<n;++i){
            for (j=0;j<m;++j){
                memset(_f2,0,sizeof(f2));
                if (mp[i][j]){
                    for (k=0;k<size;++k)if (_f1[k]){
                        nx=k; t1=getbit(nx,j); t2=getbit(nx,j+1);
                        if ( !t1 && !t2 ){
                            // # #
                            setbit(nx,j,1); setbit(nx,j+1,2);
                            _f2[nx]+=_f1[k];
                        }
                        else if ( t1==2 && t2==1 ){
                            setbit(nx,j,0); setbit(nx,j+1,0);
                            _f2[nx]+=_f1[k];
                        }
                        else if ( t1==1 && t2==1 ){
                            u=match_right(nx,j+1);
                            setbit(nx,j,0); setbit(nx,j+1,0);
                            setbit(nx,u,1);
                            _f2[nx]+=_f1[k];
                        }
                        else if ( t1==2 && t2==2 ){
                            u=match_left(nx,j);
                            setbit(nx,j,0);    setbit(nx,j+1,0);
                            setbit(nx,u,2);
                            _f2[nx]+=_f1[k];
                        }
                        else if ( t1==0 || t2==0 ){
                            _f2[nx]+=_f1[k];
                            setbit(nx,j,t2); setbit(nx,j+1,t1);
                            _f2[nx]+=_f1[k];
                        }
                    }        }
                else{
                    for (k=0;k<size;++k)
                        if (_f1[k]){
                            nx=k; t1=getbit(nx,j); t2=getbit(nx,j+1);
                            if ( t1==0 && t2==0 ){
                                _f2[nx]+=_f1[k];
                            }
                        }
                }
                tmp=_f1;_f1=_f2;_f2=tmp;
            }
            memset(_f2,0,sizeof(f2));
            for (k=0;k<(size>>2);++k)
                _f2[k<<2]=_f1[k];
            tmp=_f1; _f1=_f2; _f2=tmp;
        }
        int goal=0;
        setbit(goal,1,1);
        setbit(goal,m,2);
        //printf("%d\n",goal);
        printf("%d\n",_f1[goal]);
    }
//(改成Tony's Tour的版本)

然后~ 发现还是效率不够，不够Ural的Formula 1.于是改写成Hash写法：

Manhattan Wire还是不是清晰。。。再说吧。