LOJ #6037.「雅礼集训 2017 Day4」猜数列 状压dp

这个题的搜索可以打到48分……

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

bool must[N],in[N];

int cnt;

int n,a[N][N],q[N],b[N];

inline bool judge(int len,int lim){

  return lim-len>=cnt;

}

inline bool check(int len){

  register int i,j,k,pos,g;

  register bool can;

  for(i=;i<=n;++i){

    can=false;

    for(j=;j<=len;++j){

      if(len-j+>=a[i][]){

        pos=,g=;

        for(k=j;k<=len;++k){

          if(in[q[k]])continue;

          if(q[k]!=a[i][pos+]){g=-;break;}

          b[++pos]=q[k];

          in[q[k]]=true;

        }

        can=g!=-&&pos==a[i][];

        while(pos--)in[b[pos+]]=false;

        if(can)break;

      }

      if(j>=a[i][]){

        pos=,g=;

        for(k=j;k>;--k){

          if(in[q[k]])continue;

          if(q[k]!=a[i][pos+]){g=-;break;}

          b[++pos]=q[k];

          in[q[k]]=true;

        }

        can=g!=-&&pos==a[i][];

        while(pos--)in[b[pos+]]=false;

        if(can)break;

      }

    }

    if(!can)return false;

  }

  return true;

}

inline bool dfs(int pos,int lim){

  if(!judge(pos-,lim))return false;

  if(pos==lim+)return check(pos-);

  register int i;

  register bool keep;

  for(i=;i<=;++i)

    if(i!=q[pos-]){

      q[pos]=i;

      if(must[i]){

        must[i]=false,--cnt;

        keep=true;

      }else keep=false;

      if(dfs(pos+,lim))return true;

      if(keep)must[i]=true,++cnt;

    }

  return false;

}

int main(){

  //freopen("rio.in","r",stdin);

  scanf("%d",&n);

  register int i,j;

  for(i=;i<=n;++i){

    while(true){

      scanf("%d",&j);

      if(!j)break;

      a[i][++a[i][]]=j;

      must[j]=true;

    }

  }

  for(i=;i<=;++i)

    cnt+=must[i];

  for(i=cnt;i<=;++i){

    if(cnt<&&i==)break;

    if(dfs(,i)){

      printf("%d\n",i);

      return ;

    }

  }

  puts("-1");

  return ;

}

Kod

搜索的时候减枝实在是太重要了,其次梦想与搜索之间的平衡也是很重要的,但是一定要合理且适当.
正解很神.
贴一发题解:

还有一位大佬的代码注释也很好:https://loj.ac/submission/66283
我就是看的这两个资料,然后码出来的.(把写法从spfa改成记忆化dfs会快3倍……）
在这里说一下坑吧,就是正着走的状态可以在半截出现,倒着走的状态可以在半截消失.
分享一下代码.
正着走的单向40分:

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int F=;

const int Inf=0x3f3f3f3f;

int n,ans,full,bit[N],a[N][N],l[N],b[N];

int f[N][N][F];

bool ex[N][N],can[N][N][N],in[N],fin[N][N][F];

inline bool check(int id,int len,int to){

  register int i,pos=;

  memset(in,,sizeof(in));

  for(i=;i<=len;++i)

    in[a[id][i]]=true;

  for(i=;i<=l[to];++i){

    if(in[a[to][i]])continue;

    b[++pos]=a[to][i];

    in[a[to][i]]=true;

  }

  if(pos!=l[id]-len)return false;

  for(i=len+;i<=l[id];++i)

    if(a[id][i]!=b[i-len])

      return false;

  return true;

}

inline void dfs(int id,int pos,int st){

  //printf("%d %d %d\n",id,pos,st);

  if(fin[id][pos][st]){

    //puts("GG");

    ans=std::min(ans,f[id][pos][st]);

    return;

  }

  register int i;

  for(i=;i<=n;++i)

    if(i!=id&&(bit[i]&st)==)

      if(can[id][pos][i]&&f[i][][st|bit[id]]>f[id][pos][st]){

        f[i][][st|bit[id]]=f[id][pos][st];

        dfs(i,,st|bit[id]);

      }

  if(pos!=l[id]&&f[id][pos+][st]>f[id][pos][st]+){

    f[id][pos+][st]=f[id][pos][st]+;

    dfs(id,pos+,st);

  }

}

int main(){

  //freopen("rio.in","r",stdin);

  scanf("%d",&n);

  full=(<<n)-;

  register int i,j,k;

  for(i=;i<=n;++i){

    bit[i]=<<(i-);

    while(true){

      scanf("%d",&j);

      if(!j)break;

      a[i][++l[i]]=j;

      ex[i][j]=true;

    }

  }

  for(i=;i<=n;++i)

    for(j=;j<=l[i];++j)

      for(k=;k<=n;++k)

        can[i][j][k]=check(i,j,k);

  memset(f,0x3f,sizeof(f));

  ans=Inf;

  for(i=;i<=n;++i)

    fin[i][l[i]][full^bit[i]]=true;

  for(i=;i<=n;++i){

    f[i][][]=;

    dfs(i,,);

  }

  printf("%d\n",ans==Inf?-:ans);

  return ;

}

Kod

倒着走的单向40分:

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int F=;

const int Inf=0x3f3f3f3f;

int n,ans,full,bit[N],a[N][N],l[N],b[N];

int f[N][N][F];

bool can[N][N][N],in[N],fin[N][N][F];

inline bool check(int id,int len,int to){

  register int i,pos=;

  memset(in,,sizeof(in));

  for(i=;i<=len;++i)

    in[a[id][i]]=true;

  for(i=;i<=l[to];++i){

    if(in[a[to][i]])continue;

    b[++pos]=a[to][i];

    in[a[to][i]]=true;

  }

  if(pos!=l[id]-len)return false;

  for(i=len+;i<=l[id];++i)

    if(a[id][i]!=b[i-len])

      return false;

  return true;

}

inline void dfs(int id,int pos,int st){

  //printf("%d %d %d\n",id,pos,st);

  if(fin[id][pos][st]){

    //puts("GG");

    ans=std::min(ans,f[id][pos][st]);

    return;

  }

  if(!pos){

    register int i,j;

    for(i=;i<=n;++i)

      if(i!=id&&(bit[i]&st)==)

        for(j=;j<=l[i];++j)

          if(can[i][j][id]&&f[i][j][st|bit[id]]>f[id][pos][st]){

            f[i][j][st|bit[id]]=f[id][pos][st];

            dfs(i,j,st|bit[id]);

          }

  }

  if(pos&&f[id][pos-][st]>f[id][pos][st]+){

    f[id][pos-][st]=f[id][pos][st]+;

    dfs(id,pos-,st);

  }

}

int main(){

  //freopen("rio.in","r",stdin);

  scanf("%d",&n);

  full=(<<n)-;

  register int i,j,k;

  for(i=;i<=n;++i){

    bit[i]=<<(i-);

    while(true){

      scanf("%d",&j);

      if(!j)break;

      a[i][++l[i]]=j;

    }

  }

  for(i=;i<=n;++i)

    for(j=;j<=l[i];++j)

      for(k=;k<=n;++k)

        can[i][j][k]=check(i,j,k);

  memset(f,0x3f,sizeof(f));

  ans=Inf;

  for(i=;i<=n;++i)

    fin[i][][full^bit[i]]=true;

  for(i=;i<=n;++i){

    f[i][l[i]][]=;

    dfs(i,l[i],);

  }

  printf("%d\n",ans==Inf?-:ans);

  return ;

}

Kod

经过我不断修改的清真美丽100分代码:

#include <set>

#include <cstdio>

#include <cstring>

#include <algorithm>

typedef long long LL;

std::set<LL> ext;

const int N=;

const int F=;

const int Inf=0x3f3f3f3f;

int n,full,bit[N],a[N][N],l[N];

int f[N][N][N][N][F];

bool ex[N][N][N],can[N][N][N],in[N],vis[N][N][N][N][F];

inline bool check(int id,int len,int to){

  int i,pos=;

  memcpy(in,ex[id][len],sizeof(in));

  for(i=;i<=l[to];++i){

    if(in[a[to][i]])continue;

    ++pos,in[a[to][i]]=true;

    if(a[to][i]!=a[id][len+pos])

      return false;

  }

  if(pos!=l[id]-len)return false;

  return true;

}

inline void Init(){

  scanf("%d",&n);

  int i,j,k;

  LL key;

  for(i=;i<=n;++i){

    l[i]=,key=;

    memset(ex[i],,sizeof(ex[i]));

    bit[i]=<<(i-),j=;

    while(j){

      scanf("%d",&j);

      key=key*+j;

      a[i][++l[i]]=j;

      for(k=;k<=l[i];++k)

        if(a[i][k])

          ex[i][l[i]][a[i][k]]=true;

    }

    --l[i];

    if(ext.count(key))--i,--n;

    ext.insert(key);

  }

  full=(<<n)-;

  for(i=;i<=n;++i){

    can[][][i]=true;

    for(j=;j<=l[i];++j)

      for(k=;k<=n;++k)

        can[i][j][k]=check(i,j,k);

  }

  memset(f,0x3f,sizeof(f));

}

#define cover(id1,pos1,id2,pos2,st,add) (k=std::min(dfs(id1,pos1,id2,pos2,st)+add,k))

inline int dfs(int id1,int pos1,int id2,int pos2,int st){

  if(st==full&&pos1==l[id1]&&!pos2)return ;

  int i,j,&k=f[id1][pos1][id2][pos2][st];

  if(vis[id1][pos1][id2][pos2][st])return k;

  vis[id1][pos1][id2][pos2][st]=true;

  if(id2&&!pos2){

    for(i=;i<=n;++i)

      if(i!=id1&&!(bit[i]&st))

        for(j=;j<=l[i];++j)

          if(can[i][j][id2])

            cover(id1,pos1,i,j,st|bit[i],);

  }

  for(i=;i<=n;++i)

    if(can[id1][pos1][i]&&!(bit[i]&st))

      cover(i,,id2,pos2,st|bit[i],);

  if(pos1==l[id1]&&!pos2)return k;

  if(pos1!=l[id1]&&(ex[id2][pos2+][a[id1][pos1+]]||!id2))

    cover(id1,pos1+,id2,pos2,st,);

  if(pos2&&(ex[id1][pos1][a[id2][pos2]]||!id1))

    cover(id1,pos1,id2,pos2-,st,);

  if(pos1!=l[id1]&&pos2&&a[id2][pos2]==a[id1][pos1+])

    cover(id1,pos1+,id2,pos2-,st,);

  return k;

}

inline void Work(){

  int i,ans=Inf;

  for(i=;i<=n;++i)

    ans=std::min(dfs(,,i,l[i],bit[i]),ans);

  printf("%d\n",ans==Inf?-:ans);

}

int main(){

  Init(),Work();

  return ;

}

Kod

我第一次A掉的时候写的100分(这个代码又臭又长又屎):

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int F=;

const int Inf=0x3f3f3f3f;

int n,ans,full,bit[N],a[N][N],l[N],b[N];

int f[N][N][N][N][F];

bool ex[N][N][N],can[N][N][N],in[N],fin[N][N][N][N][F];

inline bool check(int id,int len,int to){

  register int i,pos=;

  memset(in,,sizeof(in));

  for(i=;i<=len;++i)

    in[a[id][i]]=true;

  for(i=;i<=l[to];++i){

    if(in[a[to][i]])continue;

    b[++pos]=a[to][i];

    in[a[to][i]]=true;

  }

  if(pos!=l[id]-len)return false;

  for(i=len+;i<=l[id];++i)

    if(a[id][i]!=b[i-len])

      return false;

  return true;

}

inline void dfs(int id1,int pos1,int id2,int pos2,int st){

  //printf("%d %d %d %d %d\n",id1,pos1,id2,pos2,st);

  if(fin[id1][pos1][id2][pos2][st]){

    //puts("GG");

    ans=std::min(ans,f[id1][pos1][id2][pos2][st]);

    return;

  }

  if(id2&&!pos2){

    register int i,j;

    for(i=;i<=n;++i)

      if(i!=id1&&i!=id2&&(bit[i]&st)==)

        for(j=;j<=l[i];++j)

          if(can[i][j][id2]&&f[id1][pos1][i][j][st|bit[id2]]>f[id1][pos1][id2][pos2][st]){

            f[id1][pos1][i][j][st|bit[id2]]=f[id1][pos1][id2][pos2][st];

            dfs(id1,pos1,i,j,st|bit[id2]);

          }

    if(id1){

      if(f[id1][pos1][][][st|bit[id2]]>f[id1][pos1][id2][pos2][st]){

        f[id1][pos1][][][st|bit[id2]]=f[id1][pos1][id2][pos2][st];

        dfs(id1,pos1,,,st|bit[id2]);

      }

    }else{

      for(i=;i<=n;++i)

        if(i!=id2&&(bit[i]&st)==&&f[i][][][][st|bit[id2]]>f[id1][pos1][id2][pos2][st]){

          f[i][][][][st|bit[id2]]=f[id1][pos1][id2][pos2][st];

          dfs(i,,,,st|bit[id2]);

        }

    }

  }

  if(id1){

    register int i;

    for(i=;i<=n;++i)

      if(i!=id1&&i!=id2&&(bit[i]&st)==)

        if(can[id1][pos1][i]&&f[i][][id2][pos2][st|bit[id1]]>f[id1][pos1][id2][pos2][st]){

          f[i][][id2][pos2][st|bit[id1]]=f[id1][pos1][id2][pos2][st];

          dfs(i,,id2,pos2,st|bit[id1]);

        }

  }else{

    register int i;

    for(i=;i<=n;++i)

      if(i!=id2&&(bit[i]&st)==&&f[i][][id2][pos2][st]>f[id1][pos1][id2][pos2][st]){

        f[i][][id2][pos2][st]=f[id1][pos1][id2][pos2][st];

        dfs(i,,id2,pos2,st);

      }

  }

  if((id2==||pos2==)&&(id1==||pos1==l[id1]))return;

  if(id1&&pos1!=l[id1]&&(ex[id2][pos2+][a[id1][pos1+]]||!id2)&&f[id1][pos1+][id2][pos2][st]>f[id1][pos1][id2][pos2][st]+){

    f[id1][pos1+][id2][pos2][st]=f[id1][pos1][id2][pos2][st]+;

    dfs(id1,pos1+,id2,pos2,st);

  }

  if(id2&&pos2&&(ex[id1][pos1+][a[id2][pos2]]||!id1)&&f[id1][pos1][id2][pos2-][st]>f[id1][pos1][id2][pos2][st]+){

    f[id1][pos1][id2][pos2-][st]=f[id1][pos1][id2][pos2][st]+;

    dfs(id1,pos1,id2,pos2-,st);

  }

  //printf("<>%d %d %d %d %d\n",id1,pos1,id2,pos2,st);

  if(id1&&id2&&pos2&&pos1!=l[id1]&&a[id2][pos2]==a[id1][pos1+]&&f[id1][pos1+][id2][pos2-][st]>f[id1][pos1][id2][pos2][st]+){

    //puts("OK");

    f[id1][pos1+][id2][pos2-][st]=f[id1][pos1][id2][pos2][st]+;

    dfs(id1,pos1+,id2,pos2-,st);

  }

  //else puts("NO");

}

int main(){

  //freopen("rio.in","r",stdin);

  //freopen("wq.out","w",stdout);

  scanf("%d",&n),full=(<<n)-;

  register int i,j,k;

  for(i=;i<=n;++i){

    bit[i]=<<(i-);

    while(true){

      scanf("%d",&j);

      if(!j)break;

      a[i][++l[i]]=j;

    }

  }

  for(i=;i<=n;++i)

    for(j=;j<=l[i];++j)

      for(k=;k<=n;++k)

        can[i][j][k]=check(i,j,k);

  for(i=;i<=n;++i)

    for(j=;j<=;++j)

      for(k=;k<=j;++k)

        ex[i][j][a[i][k]]=true;

  memset(f,0x3f,sizeof(f));

  ans=Inf;

  for(i=;i<=n;++i){

    for(j=;j<=n;++j){

      if(i==j)continue;

      fin[i][l[i]][j][][full^bit[i]^bit[j]]=true;

      f[i][][j][l[j]][]=;

    }

    fin[i][l[i]][][][full^bit[i]]=true;

    f[i][][][][]=;

    fin[][][i][][full^bit[i]]=true;

    f[][][i][l[i]][]=;

  }

  for(i=;i<=n;++i){

    for(j=;j<=n;++j){

      if(i==j)continue;

      dfs(i,,j,l[j],);

    }

    dfs(i,,,,);

    dfs(,,i,l[i],);

  }

  printf("%d\n",ans==Inf?-:ans);

  return ;

}

Kod

我在这里说一下我对于这道题的解法的理解吧.
看到题解之后,就会发现这道题dp的状态定义很谜.我们先看正着走单向的,我们之所以这么定义,是因为最终方案也一定是这样构成的,这很好理解.再看倒着走的,同样,我们之所以这么定义,也是因为最终方案也一定是这样构成的.那么我们再看双向的状态,思考一下,发现也是这样的.那么我们这么转移就一定没有问题.而这神奇的状态设计从哪里来呢.我觉得,就是抓出题目给出的操作的性质——“远观不如近看”,让“近看”去满足“远观”,用“远观”去匹配“近看”,再加上增量构造的思路,就迸发出了这道题的状态以及转移.
现在以我的水平,我对于这道题的理解大概也就这么多,也许以后会有更好的理解把.利用状态压缩,以及对于特殊的问题,设计合理的状态,大概就是我从这道题里学到的宝贵的东西,对于设计状态,我还是摸不着头脑的.