**这道题的数据太水了！！强烈建议管理加强数据！！
传奇英雄，精心制造Hack数据

https://www.luogu.com.cn/discuss/show/231577

以上数据可以卡掉部分洛谷和new_BZOJ（vijos）的题解。

有2种错误的解法：有人用dp[a][b][c][d]表示在(a,b)的位置，状态为c，血量为d，但是可能会遇见环的情况，导致用没有算完的状态更新了答案。（详见上面hack的那个帖子）

还有人加了一维fa，记录这个点是从哪来的。但是仍然会被卡。

那么，我们发现这道题的关键在于如何避免产生环。

本人思路：首先，我们算出当前状态可以到达那些未知或有毒的陷阱。

然后只考虑向未知或有毒的陷阱转移。

这样子，显然是没有环的。（因为向有毒的陷阱会掉1滴血，向未知的陷阱会知道未知陷阱的信息，而这样显然是不可逆的）

我们将到达终点/掉血/未知陷阱作为“一步”，而不是将一次上下左右作为“一步”

因为到达空地/已知无毒陷阱是“平淡无奇”的，没有意义，我们认为能够直接越过，不考虑。

然后，我们就愉快地A掉了这个题！

所以说，大家一定要严谨治学啊！不要以为A掉了就对了，要多加思考。

最后，祝大家省选愉快！（距离进省队还有2天）

BJ/HE/SC稳住！天佑CCF，天佑我中华！

//作者：传奇英雄
#include<bits/stdc++.h>
using namespace std;
const int g=32,g2=245,s[6]={1,3,9,27,81,243},x[4]={1,-1},y[4]={0,0,1,-1};
int m,n,k,h,sx,sy,u[g2],w,id,state,mark[g][g],m1,m2,m3;
double dp[g][g][g2][6],p[g2][6];
bool vis[g][g][g2][6],f[6],v2[g][g][g2];
char ch[g][g];
vector< pair<int,int> > v[g][g][g2];

int get(int t,int a)
{
    if(u[t]>=0) return u[t];
    for(int i=a;;i++)
        if(!(t/s[i]%3))//考虑2种情况，未知的为0或为1
            return u[t]=get(t+s[i],i+1)+get(t+(s[i]<<1),i+1);
}

void dfs2(int a,int b)
{
    for(int i=0;i<4;i++)
    {
        m1=a+x[i],m2=b+y[i];
        if(m1&&m1<=m&&m2&&m2<=n&&mark[m1][m2]!=id)
        {
            mark[m1][m2]=id;//打上标记，不走重复的点
            if(ch[m1][m2]=='.'||ch[m1][m2]==' $')//空地
                dfs2(m1,m2);
            else
            {
                if(ch[m1][m2]=='@')//目标
                {
                    for(int j=1;j<=h;j++)
                    {
                        vis[a][b][state][j]=vis[sx][sy][state][j]=1;
                        dp[a][b][state][j]=dp[sx][sy][state][j]=1;
                    }
                    return;
                }
                m3=int(ch[m1][m2])-65;//陷阱
                if(m3>=0&&m3<k)
                {
                    if(state/s[m3]%3==1)//无毒
                        dfs2(m1,m2);
                    else
                        v[sx][sy][state].push_back(make_pair(m1,m2));//有毒
                }
            }
        }
        if(vis[sx][sy][state][1])//已经到达终点
        {
            for(int j=1;j<=h;j++)
            {
                vis[a][b][state][j]=1;
                dp[a][b][state][j]=1;
            }
            return;
        }
    }
}

double dfs(int a,int b,int c,int d)
{
    if(vis[a][b][c][d])
        return dp[a][b][c][d];
    if(!v2[a][b][c])//当前状态没有被计算过
    {
        v2[a][b][c]=1;//标记已经计算过了，不重复计算
        sx=a,sy=b,state=c;//记录当前状态
        mark[a][b]=++id;//标记已经经过的位置，用id标记，省了清空
        dfs2(a,b);//计算当前状态中能到达的有毒或未知陷阱
        if(vis[a][b][c][d]) return 1;//已经到达目标
    }
    vis[a][b][c][d]=1;
    double ans=0;
    for(int i=0;i<v[a][b][c].size();i++)
    {
        int m4=v[a][b][c][i].first;
        int m5=v[a][b][c][i].second;//陷阱的坐标
        int m6=int(ch[m4][m5])-65;//陷阱的类型
        if(c/s[m6]%3)//有毒陷阱
        {
            if(d>1)//必须血量大于1才能进有毒陷阱
                ans=max(ans,dfs(m4,m5,c,d-1));
        }
        else//未知的陷阱
            if(d==1)//只有1滴血时只能进无毒的陷阱
                ans=max(ans,dfs(m4,m5,c+s[m6],d)*p[c][m6]);
            else//无毒或有毒
                ans=max(ans,dfs(m4,m5,c+s[m6],d)*p[c][m6]+dfs(m4,m5,c+(s[m6]<<1),d-1)*(1-p[c][m6]));
        if(ans==1) return dp[a][b][c][d]=1;
    }
    return dp[a][b][c][d]=ans;
}

int main()
{
    //freopen("in","r",stdin);
    scanf("%d%d%d%d\n",&m,&n,&k,&h);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%c",&ch[i][j]);
            if(ch[i][j]=='$ ')
                sx=i,sy=j;//起点的位置
        }
        scanf("\n");//注意坑人的回车
    }
    memset(u,-1,sizeof(u));
    w=(s[k]-1)>>1;
    while(w<s[k])//我们定的状态，0未知，1无毒，2有毒
    {
        scanf("%d",&u[w]);
        w++;
        for(int i=0;;i++)//将输入的编号转化为状态
            if(f[i])
            {
                f[i]=0;
                w+=s[i];
            }
            else
            {
                f[i]=1;
                break;
            }
    }
    for(int i=0;i<s[k];i+=3)//末位为1或2的显然已经不用考虑，因为计算i-1的时候已经算过了，i-1最后1位加1
        get(i,0);//计算未知的所有可能之和
    for(int i=0;i<s[k];i++)
        for(int j=0;j<k;j++)
            if(!(i/s[j]%3))
                p[i][j]=u[i+s[j]]*1.0/(u[i+s[j]]+u[i+(s[j]<<1)]);//计算概率
    printf("%.3f",dfs(sx,sy,0,h));
    return 0;
}

#1 Hack

5 3 3 2
#@#
BA#
BBB
AAC
B$.
12 3 28 7 12 3 28 7

输出：
0.800

解释：一路向上。（将枚举4个方向的顺序改成下上右左，就会出错）

#2 hack

5 2 1 2
@#
.#
A$
A.
#A
1 1

输出：1.000（有2滴血，最多进1个陷阱，肯定不会死）

这组数据卡掉加一维记录fa的做法

#3 hack

3 3 2 2
A.B
$#B
AA@
2 1 2 5

输出：0.500

解释：正解可能重复经过1个点。

概率DP+记忆化搜索
k≤5，明显要状态压缩。
设f[i][j][k][l]表示在i行j列，当时的状态为k，血量为l的概率。
其中i为一个三进制数，每一位表示陷阱的状态（0-无害，1-有害，2-未知）
考虑如何转移
设前往的点是（x，y）

1. （x，y）是空地，直接转移即可。
2. 考虑（x，y）是空地的情况：

　　若这个陷阱是无害的，与空地相同
　　f[i][j][k][l]=max(f[i][j][k][l], f[x][y][k][l])
　　若这个陷阱有害，则扣一滴血转移
　　f[i][j][k][l]=max(f[i][j][k][l], f[x][y][k][l - 1])
　　如果未知则分两种情况转移
　　f[i][j][k][l]=max(f[i][j][k][l],g[k][i']×f[x][y][k][l-1]+(1-g[k][i'])×f[x][y][k][l])
　　其中g[i][j]表示在i情况下j为有害陷阱的概率

考虑如何求g数组：
每次dfs枚举每中陷阱的状态，暴力找出合乎条件的p值，统计即可

#include <cstdio>
#include <cstdlib>
using namespace std;
#define Id(x) (x - 'A')

const int maxn = 35, maxp = 6;
const int pow[6] = {1, 3, 9, 27, 81, 243};
const int d[4][2] = {1, 0, 0, -1, -1, 0, 0, 1};
char Map[maxn][maxn];
int n, m, K, H, p[maxn];

int state[10];
double g[250][maxp];
void dfs(int now, int sum, int tot)
{
    if(now == K) {
        //if(tot == 5)
        //  printf("call me");
        for(int i = 0; i < K; ++i)
            if(state[i] == 2) {
                int sum1 = 0, sum2 = 0;
                for(int l, j = 0; j < (1 << K); ++j) {
                    for(l = 0; l < K; ++l)
                        if(state[l] < 2 && ((bool)(j & (1 << l))) != state[l]) break;
                    if(l < K) continue;
                    sum1 += p[j], sum2 += (j & (1 << i)) ? p[j] : 0;
                }
                g[tot][i] = (double)sum2 / sum1;
            }
        return; //!!!
    }
    for(int i = 0; i < 3; ++i)
        state[now] = i, dfs(now + 1, sum + (i == 1 ? (1 << now) : 0), tot + pow[now] * i);
}

inline void chkmax(double &a, double b)
{
    if(a < b) a = b;
}

inline int know(int k, int type)
{
    for(int i = K - 1; i > type; --i)
        k %= pow[i];
    return k / pow[type];
}

double ans, f[maxn][maxn][250][maxp];
bool vis[maxn][maxn][250][maxp];
double dfs(int i, int j, int k, int l) //位于(x, y),状态为k,血量为l的最大求生概率
{
    if(Map[i][j] == '@') return 1.;
    if(l < 1) return 0;
    if(vis[i][j][k][l]) return f[i][j][k][l];
    double &p = f[i][j][k][l];
    vis[i][j][k][l] = true;
    for(int c = 0; c < 4; ++c) {
        int x = i + d[c][0], y = j + d[c][1];
        if(x < 1 || x > m || y < 1 || y > n) continue; //越界
        if(Map[x][y] == '#') continue; //墙
        if(Map[x][y] == '.' || Map[x][y] == '$' || Map[x][y] == '@') { //空地
            chkmax(p, dfs(x, y, k, l));
        }else { //陷阱
            int type = Id(Map[x][y]), state = know(k, type);
            if(state == 0) { //无害
                chkmax(p, dfs(x, y, k, l));
            }else if(state == 1) { //有害
                chkmax(p, dfs(x, y, k, l - 1));
            }else {
                chkmax(p, g[k][type] * dfs(x, y, k - pow[type], l - 1) + (1 - g[k][type]) * dfs(x, y, k - 2 * pow[type], l));
                //printf("%d %d %d %d: %.3lf %.3lf\n", i, j, k, l, (1 - g[k][type]) * dfs(x, y, k - 2 * pow[type], l), g[k][type] * dfs(x, y, k - pow[type], l - 1));
            }
        }
    }
    return p;
}

int main()
{
    freopen("maze.in", "r", stdin);
    freopen("maze.out", "w", stdout);
    scanf("%d%d%d%d\n", &m, &n, &K, &H);
    int x, y;
    for(int i = 1; i <= m; ++i) {
        scanf("%s\n", Map[i] + 1);
        for(int j = 1; j <= n; ++j)
            if(Map[i][j] == '$') x = i, y = j;
    }
    for(int i = 0; i < (1 << K); ++i) scanf("%d", &p[i]);
    dfs(0, 0, 0);
    printf("%.3lf", dfs(x, y, pow[K] - 1, H));
    return 0;
}

p.s.
1:如果你得了90分，检查一下搜索顺序
2:如果你在vijos上AC，其他ojRE/WA请检查读入，因为别的oj字符串后有空格
3:我在讨论里放了一组数据。
4:我这题解不知多少年后才会被别人看到了。