Description

Solution

用三进制表示陷阱状态，1表示有害，2表示无害，0表示不知道

用\(f[S][i]\)表示状态为S时陷阱i有害的概率，这个可以预处理出

\(d[S][i][j][h]\)表示状态为S，在坐标\((i,j)\)，血量为h时的答案

然后就可以DP了，记忆化搜索

Code

#include 
    
     #include 
     
      #define db double#define Sta 300#define N 36using namespace std;const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};db dp[Sta][N][N][6],f[Sta][N];int n,m,k,h,p[N],sx,sy,A[6]; char g[N][N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}db tmp[2];void dfs(int x){    if(x==k){        int S=0;        for(int i=k-1;i>=0;--i) S=S*3+A[i];        for(int i=0;i
      
       >l)&1)){flag=1;break;}                if(flag) continue;                tmp[(j>>i)&1]+=p[j];            }            f[S][i]=tmp[1]/(tmp[1]+tmp[0]);        }    }else for(int i=0;i<=2;++i){A[x]=i;dfs(x+1);}}int Change(int S,int pos,int x){    for(int i=0;i
       
        =0;--i) S=S*3+A[i];    return S;} db DP(int S,int x,int y,int h){    if(!h) return 0;    if(g[x][y]=='@') return 1;    db &tmp=dp[S][x][y][h];    if(tmp!=-1) return tmp;    tmp=0;        for(int d=0;d<4;++d){        int nx=x+dx[d],ny=y+dy[d],tS=S;        if(nx<=0||ny<=0||nx>n||ny>m) continue;        char ch=g[nx][ny];        if(ch=='#') continue;        else if(ch=='.'||ch=='$'||ch=='@') tmp=max(tmp,DP(S,nx,ny,h));        else if(ch>='A'&&ch<='Z'){            int id=ch-'A';            for(int i=0;i