BZOJ2512 : Groc

最优解一定是将起点、终点以及所有必经点连接成一棵树，对于每条树边恰好走两次，而从起点到终点的一条路径只走一次。

考虑连通性DP，设$f[i][j][k][x]$表示考虑完前$i$个走道，第$i$个走道底部和上部是否存在于树中，底部和上部是否和起点连通，走一次的路径端点是底部还是上部时的最小代价。

时间复杂度$O(NA^2)$。

#include<cstdio>

const int N=360,inf=100000000;

int m,n,A,B,i,j,k,x,a,b,nj,nk,nx,w,v[N][30],f[N][4][4][2],ans;

inline void up(int&a,int b){a>b?(a=b):0;}

inline int sum(int x,int l,int r){

  int t=v[x][r];

  if(l)t-=v[x][l-1];

  return t;

}

int main(){

  scanf("%d%d%d%d",&m,&n,&A,&B);A++;

  while(m--)scanf("%d%d",&i,&j),v[i][j]=1;

  for(i=0;i<=n;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(x=0;x<2;x++)f[i][j][k][x]=inf;

  f[0][1][1][0]=-B;

  for(i=1;i<=n;i++)for(j=1;j<=A;j++)v[i][j]+=v[i][j-1];

  for(i=0;i<n;i++)for(j=0;j<4;j++)for(k=1;k<4;k++)for(x=0;x<2;x++)if(f[i][j][k][x]<inf){

    w=f[i][j][k][x];

    for(a=0;a<=A;a++){

      if(sum(i+1,0,a)<sum(i+1,0,A))continue;

      nj=1;

      if(a==A)nj|=2;

      nk=k&1;

      if((j>>1)&&!(k>>1))continue;

      if(a==A)nk|=(k&1)<<1;

      if(x==0){

        up(f[i+1][nj][nk][0],w+B+a*2);

        if(a==A)up(f[i+1][nj][nk][1],w+B+A);

      }

    }

    for(a=0;a<=A;a++){

      if(sum(i+1,a,A)<sum(i+1,0,A))continue;

      nj=2;

      if(a==0)nj|=1;

      nk=(k>>1)<<1;

      if((j&1)&&!(k&1))continue;

      if(a==0)nk|=k>>1;

      if(x==1){

        up(f[i+1][nj][nk][1],w+B+(A-a)*2);

        if(a==0)up(f[i+1][nj][nk][0],w+B+A);

      }

    }

    for(a=0;a<=A;a++)for(b=a+1;b<=A;b++){

      if(sum(i+1,0,a)+sum(i+1,b,A)<sum(i+1,0,A))continue;

      nj=3;

      nk=k;

      up(f[i+1][nj][nk][x],w+B*3+(a+A-b)*2);

      nk=k&1;

      if(x==0)if(!(j>>1)||(k>>1))up(f[i+1][nj][nk][0],w+B+(a+A-b)*2);

      nk=(k>>1)<<1;

      if(x==1)if(!(j&1)||(k&1))up(f[i+1][nj][nk][1],w+B+(a+A-b)*2);

    }

    up(f[i+1][3][3][x],w+B*3+A*2);

    up(f[i+1][3][3][x^1],w+B*3+A);

  }

  ans=f[n][1][1][0];

  up(ans,f[n][3][3][0]);

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

}