自动搬运

查看原文

来自洛谷，原作者为

	传奇英雄 鞠躬尽瘁，让bug死而后已

搬运于2025-08-24 21:38:17，当前版本为作者最后更新于2020-06-19 08:41:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

**这道题的数据太水了！！强烈建议管理加强数据！！

传奇英雄，精心制造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;
}

本题思路来自chdy大佬。他的代码也是对的。感谢大佬！

不建议删掉错误的题解。因为错误的题解确实也是一种很好的思路。（建议各位大佬学习一下错误的题解，然后认真思考一下为什么错了）做走迷宫问题的时候一定要注意环的问题。