天天看点
返回

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

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

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=12;
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=1;i<=n;++i){
    can=false;
    for(j=1;j<=len;++j){
      if(len-j+1>=a[i][0]){
        pos=0,g=0;
        for(k=j;k<=len;++k){
          if(in[q[k]])continue;
          if(q[k]!=a[i][pos+1]){g=-1;break;}
          b[++pos]=q[k];
          in[q[k]]=true;
        }
        can=g!=-1&&pos==a[i][0];
        while(pos--)in[b[pos+1]]=false;
        if(can)break;
      }
      if(j>=a[i][0]){
        pos=0,g=0;
        for(k=j;k>0;--k){
          if(in[q[k]])continue;
          if(q[k]!=a[i][pos+1]){g=-1;break;}
          b[++pos]=q[k];
          in[q[k]]=true;
        }
        can=g!=-1&&pos==a[i][0];
        while(pos--)in[b[pos+1]]=false;
        if(can)break;
      }
    }
    if(!can)return false;
  }
  return true;
}
inline bool dfs(int pos,int lim){
  if(!judge(pos-1,lim))return false;
  if(pos==lim+1)return check(pos-1);
  register int i;
  register bool keep;
  for(i=1;i<=9;++i)
    if(i!=q[pos-1]){
      q[pos]=i;
      if(must[i]){
        must[i]=false,--cnt;
        keep=true;
      }else keep=false;
      if(dfs(pos+1,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=1;i<=n;++i){
    while(true){
      scanf("%d",&j);
      if(!j)break;
      a[i][++a[i][0]]=j;
      must[j]=true;
    }
  }
  for(i=1;i<=9;++i)
    cnt+=must[i];
  for(i=cnt;i<=10;++i){
    if(cnt<5&&i==10)break;
    if(dfs(1,i)){
      printf("%d\n",i);
      return 0;
    }
  }
  puts("-1");
  return 0;
}

Kod

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

正解很神.

贴一发题解:

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

还有一位大佬的代码注释也很好:https://loj.ac/submission/66283

我就是看的这两个资料,然后码出来的.(把写法从spfa改成记忆化dfs会快3倍……）

在这里说一下坑吧,就是正着走的状态可以在半截出现,倒着走的状态可以在半截消失.

分享一下代码.

正着走的单向40分:

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=12;
const int F=2010;
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=0;
  memset(in,0,sizeof(in));
  for(i=1;i<=len;++i)
    in[a[id][i]]=true;
  for(i=1;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+1;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=1;i<=n;++i)
    if(i!=id&&(bit[i]&st)==0)
      if(can[id][pos][i]&&f[i][0][st|bit[id]]>f[id][pos][st]){
        f[i][0][st|bit[id]]=f[id][pos][st];
        dfs(i,0,st|bit[id]);
      }
  if(pos!=l[id]&&f[id][pos+1][st]>f[id][pos][st]+1){
    f[id][pos+1][st]=f[id][pos][st]+1;
    dfs(id,pos+1,st);
  }
}
int main(){
  //freopen("rio.in","r",stdin);
  scanf("%d",&n);
  full=(1<<n)-1;
  register int i,j,k;
  for(i=1;i<=n;++i){
    bit[i]=1<<(i-1);
    while(true){
      scanf("%d",&j);
      if(!j)break;
      a[i][++l[i]]=j;
      ex[i][j]=true;
    }
  }
  for(i=1;i<=n;++i)
    for(j=0;j<=l[i];++j)
      for(k=1;k<=n;++k)
        can[i][j][k]=check(i,j,k);
  memset(f,0x3f,sizeof(f));
  ans=Inf;
  for(i=1;i<=n;++i)
    fin[i][l[i]][full^bit[i]]=true;
  for(i=1;i<=n;++i){
    f[i][0][0]=0;
    dfs(i,0,0);
  }
  printf("%d\n",ans==Inf?-1:ans);
  return 0;
}

Kod

倒着走的单向40分:

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=12;
const int F=2010;
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=0;
  memset(in,0,sizeof(in));
  for(i=1;i<=len;++i)
    in[a[id][i]]=true;
  for(i=1;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+1;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=1;i<=n;++i)
      if(i!=id&&(bit[i]&st)==0)
        for(j=0;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-1][st]>f[id][pos][st]+1){
    f[id][pos-1][st]=f[id][pos][st]+1;
    dfs(id,pos-1,st);
  }
}
int main(){
  //freopen("rio.in","r",stdin);
  scanf("%d",&n);
  full=(1<<n)-1;
  register int i,j,k;
  for(i=1;i<=n;++i){
    bit[i]=1<<(i-1);
    while(true){
      scanf("%d",&j);
      if(!j)break;
      a[i][++l[i]]=j;
    }
  }
  for(i=1;i<=n;++i)
    for(j=0;j<=l[i];++j)
      for(k=1;k<=n;++k)
        can[i][j][k]=check(i,j,k);
  memset(f,0x3f,sizeof(f));
  ans=Inf;
  for(i=1;i<=n;++i)
    fin[i][0][full^bit[i]]=true;
  for(i=1;i<=n;++i){
    f[i][l[i]][0]=0;
    dfs(i,l[i],0);
  }
  printf("%d\n",ans==Inf?-1:ans);
  return 0;
}

Kod

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

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
std::set<LL> ext;
const int N=11;
const int F=1050;
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=0;
  memcpy(in,ex[id][len],sizeof(in));
  for(i=1;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=1;i<=n;++i){
    l[i]=0,key=0;
    memset(ex[i],0,sizeof(ex[i]));
    bit[i]=1<<(i-1),j=1;
    while(j){
      scanf("%d",&j);
      key=key*10+j;
      a[i][++l[i]]=j;
      for(k=1;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=(1<<n)-1;
  for(i=1;i<=n;++i){
    can[0][0][i]=true;
    for(j=0;j<=l[i];++j)
      for(k=1;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 0;
  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=0;i<=n;++i)
      if(i!=id1&&!(bit[i]&st))
        for(j=0;j<=l[i];++j)
          if(can[i][j][id2])
            cover(id1,pos1,i,j,st|bit[i],0);
  }
  for(i=1;i<=n;++i)
    if(can[id1][pos1][i]&&!(bit[i]&st))
      cover(i,0,id2,pos2,st|bit[i],0);
  if(pos1==l[id1]&&!pos2)return k;
  if(pos1!=l[id1]&&(ex[id2][pos2+1][a[id1][pos1+1]]||!id2))
    cover(id1,pos1+1,id2,pos2,st,1);
  if(pos2&&(ex[id1][pos1][a[id2][pos2]]||!id1))
    cover(id1,pos1,id2,pos2-1,st,1);
  if(pos1!=l[id1]&&pos2&&a[id2][pos2]==a[id1][pos1+1])
    cover(id1,pos1+1,id2,pos2-1,st,1);
  return k;
}
inline void Work(){
  int i,ans=Inf;
  for(i=1;i<=n;++i)
    ans=std::min(dfs(0,0,i,l[i],bit[i]),ans);
  printf("%d\n",ans==Inf?-1:ans);
}
int main(){
  Init(),Work();
  return 0;
}

Kod

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

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=12;
const int F=1112;
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=0;
  memset(in,0,sizeof(in));
  for(i=1;i<=len;++i)
    in[a[id][i]]=true;
  for(i=1;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+1;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=1;i<=n;++i)
      if(i!=id1&&i!=id2&&(bit[i]&st)==0)
        for(j=0;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][0][0][st|bit[id2]]>f[id1][pos1][id2][pos2][st]){
        f[id1][pos1][0][0][st|bit[id2]]=f[id1][pos1][id2][pos2][st];
        dfs(id1,pos1,0,0,st|bit[id2]);
      }
    }else{
      for(i=1;i<=n;++i)
        if(i!=id2&&(bit[i]&st)==0&&f[i][0][0][0][st|bit[id2]]>f[id1][pos1][id2][pos2][st]){
          f[i][0][0][0][st|bit[id2]]=f[id1][pos1][id2][pos2][st];
          dfs(i,0,0,0,st|bit[id2]);
        }
    }
  }
  if(id1){
    register int i;
    for(i=1;i<=n;++i)
      if(i!=id1&&i!=id2&&(bit[i]&st)==0)
        if(can[id1][pos1][i]&&f[i][0][id2][pos2][st|bit[id1]]>f[id1][pos1][id2][pos2][st]){
          f[i][0][id2][pos2][st|bit[id1]]=f[id1][pos1][id2][pos2][st];
          dfs(i,0,id2,pos2,st|bit[id1]);
        }
  }else{
    register int i;
    for(i=1;i<=n;++i)
      if(i!=id2&&(bit[i]&st)==0&&f[i][0][id2][pos2][st]>f[id1][pos1][id2][pos2][st]){
        f[i][0][id2][pos2][st]=f[id1][pos1][id2][pos2][st];
        dfs(i,0,id2,pos2,st);
      }
  }
  if((id2==0||pos2==0)&&(id1==0||pos1==l[id1]))return;
  if(id1&&pos1!=l[id1]&&(ex[id2][pos2+1][a[id1][pos1+1]]||!id2)&&f[id1][pos1+1][id2][pos2][st]>f[id1][pos1][id2][pos2][st]+1){
    f[id1][pos1+1][id2][pos2][st]=f[id1][pos1][id2][pos2][st]+1;
    dfs(id1,pos1+1,id2,pos2,st);
  }
  if(id2&&pos2&&(ex[id1][pos1+1][a[id2][pos2]]||!id1)&&f[id1][pos1][id2][pos2-1][st]>f[id1][pos1][id2][pos2][st]+1){
    f[id1][pos1][id2][pos2-1][st]=f[id1][pos1][id2][pos2][st]+1;
    dfs(id1,pos1,id2,pos2-1,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+1]&&f[id1][pos1+1][id2][pos2-1][st]>f[id1][pos1][id2][pos2][st]+1){
    //puts("OK");
    f[id1][pos1+1][id2][pos2-1][st]=f[id1][pos1][id2][pos2][st]+1;
    dfs(id1,pos1+1,id2,pos2-1,st);
  }
  //else puts("NO");
}
int main(){
  //freopen("rio.in","r",stdin);
  //freopen("wq.out","w",stdout);
  scanf("%d",&n),full=(1<<n)-1;
  register int i,j,k;
  for(i=1;i<=n;++i){
    bit[i]=1<<(i-1);
    while(true){
      scanf("%d",&j);
      if(!j)break;
      a[i][++l[i]]=j;
    }
  }
  for(i=1;i<=n;++i)
    for(j=0;j<=l[i];++j)
      for(k=1;k<=n;++k)
        can[i][j][k]=check(i,j,k);
  for(i=1;i<=n;++i)
    for(j=0;j<=11;++j)
      for(k=1;k<=j;++k)
        ex[i][j][a[i][k]]=true;
  memset(f,0x3f,sizeof(f));
  ans=Inf;
  for(i=1;i<=n;++i){
    for(j=1;j<=n;++j){
      if(i==j)continue;
      fin[i][l[i]][j][0][full^bit[i]^bit[j]]=true;
      f[i][0][j][l[j]][0]=0;
    }
    fin[i][l[i]][0][0][full^bit[i]]=true;
    f[i][0][0][0][0]=0;
    fin[0][0][i][0][full^bit[i]]=true;
    f[0][0][i][l[i]][0]=0;
  } 
  for(i=1;i<=n;++i){
    for(j=1;j<=n;++j){
      if(i==j)continue;
      dfs(i,0,j,l[j],0);
    }
    dfs(i,0,0,0,0);
    dfs(0,0,i,l[i],0);
  }
  printf("%d\n",ans==Inf?-1:ans);
  return 0;
}

Kod

我在这里说一下我对于这道题的解法的理解吧.

看到题解之后,就会发现这道题dp的状态定义很谜.我们先看正着走单向的,我们之所以这么定义,是因为最终方案也一定是这样构成的,这很好理解.再看倒着走的,同样,我们之所以这么定义,也是因为最终方案也一定是这样构成的.那么我们再看双向的状态,思考一下,发现也是这样的.那么我们这么转移就一定没有问题.而这神奇的状态设计从哪里来呢.我觉得,就是抓出题目给出的操作的性质——“远观不如近看”,让“近看”去满足“远观”,用“远观”去匹配“近看”,再加上增量构造的思路,就迸发出了这道题的状态以及转移.

现在以我的水平,我对于这道题的理解大概也就这么多,也许以后会有更好的理解把.利用状态压缩,以及对于特殊的问题,设计合理的状态,大概就是我从这道题里学到的宝贵的东西,对于设计状态,我还是摸不着头脑的.

转载于:https://www.cnblogs.com/TSHugh/p/8625433.html

数据结构与算法
上一篇: mysql 建立外键出现的问题
下一篇: 事务（ACID）、并发一致性问题（丢失修改、读脏数据、不可重复读、幻影读）、封锁（封锁粒度、类型、协议、MySQL 隐式与显示锁定）

继续阅读