luogu P4206 [NOI2005]聪聪与可可期望dp 记忆化搜索

这道题的核心是想到如何统计答案。

如果设f[i][j]表示第i个时刻... 可以发现还需要统计位置信息以及上一次到底被抓到没有的东西不太好做。

两者的位置都在变化所以需要设出状态 f[i][j]表示第聪聪在i位置可可在j位置的期望步数。

容易想到转移. i==j->0 j是i的下一步或者下下一步期望为1.

由于聪聪的走位是固定的所以设其走两步的位置为 w 而可可是随机的所以只需要枚举一下可可的转移即可。

由于状态的无序转移性所以需要记忆化搜索。非常有趣。

值得一提的是预处理j的下一步位置需要使用迪杰斯特拉这样复杂度是n^2log的。

const int MAXN=1010;

int n,m,len,S,T;

db f[MAXN][MAXN];

int ne[MAXN][MAXN],a[MAXN][MAXN];

int dis[MAXN],vis[MAXN],du[MAXN],mark[MAXN][MAXN];

int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];

priority_queue<pii>q;

inline void add(int x,int y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

	++du[y];

}

inline db dfs(int x,int y)

{

	if(mark[x][y])return f[x][y];

	mark[x][y]=1;

	if(x==y)return f[x][y]=0;

	if(ne[x][y]==y||ne[ne[x][y]][y]==y)return f[x][y]=1;

	int w=ne[ne[x][y]][y];

	++f[x][y];

	go(y)f[x][y]+=1.0/du[y]*dfs(w,tn);

	f[x][y]+=1.0/du[y]*dfs(w,y);

	return f[x][y];

}

inline void dij(int s)

{

	for(int i=1;i<=n;++i)dis[i]=INF;

	q.push(mk(0,s));

	dis[s]=0;

	while(q.size())

	{

		int x=q.top().S;

		q.pop();

		if(vis[x])continue;

		vis[x]=1;

		for(int i=lin[x];i;i=nex[i])

		{

			int tn=ver[i];

			if(dis[tn]>dis[x]+1)

			{

				dis[tn]=dis[x]+1;

				q.push(mk(-dis[tn],tn));

			}

		}

	}

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);

	get(S);get(T);

	rep(1,m,i)

	{

		int x,y;

		get(x);get(y);

		add(x,y);add(y,x);

	}

	rep(1,n,i)

	{

		dij(i);++du[i];

		rep(1,n,j)a[i][j]=dis[j],vis[j]=0;

	}

	rep(1,n,i)rep(1,n,j)

	{

		int maxx=INF,p=0;

		for(int k=lin[i];k;k=nex[k])

		{

			int tn=ver[k];

			if(a[j][tn]==maxx)p=min(p,tn);

			if(a[j][tn]<maxx)maxx=a[j][tn],p=tn;

		}

		ne[i][j]=p;

	}

	printf("%.3lf",dfs(S,T));

	return 0;

}

巴特西

luogu P4206 [NOI2005]聪聪与可可期望dp 记忆化搜索

最新文章

热门文章

巴特西

luogu P4206 [NOI2005]聪聪与可可 期望dp 记忆化搜索

最新文章

热门文章

luogu P4206 [NOI2005]聪聪与可可期望dp 记忆化搜索