BZOJ 2246 [SDOI2011]迷宫探险 (记忆化搜索)

题目大意：太长了，略

bzoj luogu

并没有想到三进制状压

题解：

3进制状压陷阱的状态，0表示这种陷阱的状态未知，1已知危险，2已知不危险

然后预处理出在当前状态下，每种陷阱有害的概率，设为$g[s][i]$

已知是危险的，有害概率为1

已知是不危险的，有害概率为0

未知的部分用概率表格里符合当前状态的部分，才是正确的(比如第4个样例输出了0.857就是没用这种方法去求概率)

定义$f[x][y][s][h]$表示当前在(x,y)，陷阱的状态为s，当前血量是h

然后记忆化爆搜即可

...

此题解针对在luogu上交了，WA了第2个/第8个/第10个点，然后“换了个枚举顺序”就恰好A掉了这道题的情况

仔细观察发现上面那种做法貌似是有一些问题的

比如从上一层xxxx往下走↓，走到了yyyy这个状态，然后，yyyy还会往上跑从xxxx更新，得到了一个#$%@的“最优解”，这可能是yyyy往上跑的最优解，但也可能不是！

因为你状态xxxx可能还有某个方向没有遍历，但我们草率得把f[xxxx]这个“并不最优解”去更新f[yyyy]

那如果在另一次搜索中，由某个状态zzzz往上走↑，又跑到了yyyy，由于访问过了yyyy，所以返回了f[yyyy]，然而这个f[yyyy]可能并不是最优解，导致答案出错！

为了避免这种错误，我们额外记录一维，表示从那个方向跑到当前状态，$f[x][y][s][h][t]$，t表示上一层是从哪个方向来的即可，虽然牺牲了一些常数但保证了答案的正确性！

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 35

 #define M 250

 #define dd double

 #define idx(x) (x-'A'+1)

 using namespace std;

 int n,m,sx,sy,K,H;

 char str[N][N];

 int xx[]={-,,,},yy[]={,,,-};

 int pw[]={,,,,,,};

 int mp[N][N],pro[M];

 dd f[N][N][M][][5],g[M][],dan[];

 bool vis[N][N][M][][];

 bool check(int x,int y){

     if(x<||x>n||y<||y>m||mp[x][y]==-) return ;

     else return ;}

 int p[M][];

 dd dfs(int x,int y,int s,int h,int fa)

 {

     if(h<=) return ;

     if(vis[x][y][s][h][fa]) return f[x][y][s][h][fa];

     vis[x][y][s][h][fa]=;

     if(mp[x][y]==K+){

         f[x][y][s][h][fa]=;

         return ;

     }int tx,ty,t1,t2,pt;

     dd tmp=;

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

     {

         tx=x+xx[i],ty=y+yy[i];

         if(!check(tx,ty)) continue;

         pt=mp[tx][ty],t1=t2=s;

         dd ans1=,ans2=;

         if(pt>&&pt<=K&&!p[s][pt]) t1+=(*pw[pt-]);

         if(pt>&&pt<=K&&!p[s][pt]) t2+=(*pw[pt-]);

         if(pt!=-){

             if(g[s][pt]>0.0&&h>) ans1=dfs(tx,ty,t1,h-,(i+)%);

             if(g[s][pt]<1.0)ans2=dfs(tx,ty,t2,h,(i+)%);

             tmp=max(tmp,1.0*g[s][pt]*ans1+(1.0-g[s][pt])*ans2);

         }

     }f[x][y][s][h][fa]=tmp;

     return f[x][y][s][h][fa];

 }

 void Pre()

 {

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

         scanf("%d",&pro[i]);

     for(int i=;i<pw[K];i++){

         int x=i,k=K;

         while(k){

             p[i][k]=x/pw[k-];

             x%=pw[k-],k--;}

     }

     for(int i=;i<pw[K];i++)

     {

         int tot=,sum;

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

             dan[j+]=;

         for(int s=;s<(<<K);s++){

             int fl=;

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

                 if((s&(<<j))&&p[i][j+]==) {fl=;break;}

                 else if((!(s&(<<j)))&&p[i][j+]==) {fl=;break;}

             if(!fl) continue;

             tot+=pro[s];

         }int x=i,k=K;

         for(int k=;k<=K;k++)

         {

             if(p[i][k]==){

                 sum=;

                 for(int s=;s<(<<K);s++)

                 {

                     int fl=;

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

                         if((s&(<<j))&&p[i][j+]==) {fl=;break;}

                         else if((!(s&(<<j)))&&p[i][j+]==) {fl=;break;}

                     if(!fl) continue;

                     if(s&(<<(k-))) sum+=pro[s];

                 }g[i][k]=1.0*sum/tot;

             }

             if(p[i][k]==){g[i][k]=1.0;}

             if(p[i][k]==){g[i][k]=0.0;}

         }

     }

 }

 int main()

 {

     scanf("%d%d%d%d",&n,&m,&K,&H);

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

         scanf("%s",str[i]+);

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

         if(str[i][j]=='$') sx=i,sy=j;

         else if(str[i][j]=='@') mp[i][j]=K+;

         else if(str[i][j]=='#') mp[i][j]=-;

         else if(str[i][j]=='.') mp[i][j]=;

         else mp[i][j]=idx(str[i][j]);

     }

     Pre();

     printf("%.3lf\n",dfs(sx,sy,,H,));

     return ;

 }

巴特西

BZOJ 2246 [SDOI2011]迷宫探险 (记忆化搜索)

最新文章

热门文章