BZOJ4707 : B君的技巧

建立线段树，设$f[x][l][r]$表示当前考虑$x$点，最左端是$l$，最右端是$r$的最少代价。

如果$a$在$x<<1$，$d$在$x<<1|1$，

设$g[a][c]=\min(f[x<<1][a][b]+w[b][c])$，

则$f[x][a][d]=\min(g[a][c]+f[x<<1|1][c][d])$。

对于$a$在$x<<1|1$，$d$在$x<<1$的情况可以类似处理。

时间复杂度$O(n^3)$。

对于空间上的优化，因为对于同一深度的每个$x$来说，其有效的$l,r$的取值区间互不相交，所以可以省去$x$这一维。

空间复杂度$O(n^2)$。

#include<cstdio>

const int N=515,inf=~0U>>2;

int K,n,m,m2,i,j,l,r,mid,x,y,z,ans,w[N][N],f[N][N],g[N][N],h[N][N];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void up(int&a,int b){if(a>b)a=b;}

int main(){

  read(K);n=1<<K;

  for(i=0;i<n;i++)for(j=0;j<n;j++)read(w[i][j]);

  m=1;

  while(K--){

    m2=m;m<<=1;

    for(l=0;l<n;l+=m){

      r=l+m,mid=l+m2;

      for(x=l;x<mid;x++)for(z=mid;z<r;z++){

        g[x][z]=inf;

        for(y=l;y<mid;y++)up(g[x][z],f[x][y]+w[y][z]);

      }

      for(x=mid;x<r;x++)for(z=l;z<mid;z++){

        g[x][z]=inf;

        for(y=mid;y<r;y++)up(g[x][z],f[x][y]+w[y][z]);

      }

      for(x=l;x<mid;x++)for(z=mid;z<r;z++){

        h[x][z]=inf;

        for(y=mid;y<r;y++)up(h[x][z],g[x][y]+f[y][z]);

      }

      for(x=mid;x<r;x++)for(z=l;z<mid;z++){

        h[x][z]=inf;

        for(y=l;y<mid;y++)up(h[x][z],g[x][y]+f[y][z]);

      }

      for(x=l;x<r;x++)for(y=l;y<r;y++)f[x][y]=inf;

      for(x=l;x<mid;x++)for(y=mid;y<r;y++)f[x][y]=h[x][y];

      for(x=mid;x<r;x++)for(y=l;y<mid;y++)f[x][y]=h[x][y];

    }

  }

  ans=inf;

  for(i=0;i<n;i++)for(j=0;j<n;j++)up(ans,f[i][j]);

  return printf("%d",ans),0;

}

巴特西

BZOJ4707 : B君的技巧

最新文章

热门文章