[NOI2005] 聪聪与可可

时间:2022-09-11 11:26:18

机器猫の传送门


期望DP+记搜

聪聪一直在向可可方向追,所以不会回到原处,不具有后效性,考虑用概率与期望DP+记忆化搜索求解

用dp[x][y]表示可可在x点,聪聪在y点时步数的期望值

判断边界

①当x==y时结束 (此时毫无疑问的,dp[x][y]=0)

②当x!=y时 若x与y的距离等于1或2时则dp[x][y]=1
(原因:若x距离y只有一步,则dp[x][y]=1;若x距离y两步,因为x也可一次移动两步,两者依旧可以通过一次重合,dp[x][y]=1)

预处理

对图中每个x,到y的最短距离(BFS求单源最短路径 O(n^2),不会的也可以BDFS自行学习广搜),将当前y的下一个位置预处理为nex(x,y)

推导

根据期望的定义得到递推式dp[x]=∑1/(p+1)*dp[x’][nex(x,nex(x,y))]

(1/(p+1)为到达每一个新状态的概率,然后就根据两步之内可能的状态进行递推,对其进行求和,即为当前的期望步数)

AT LAST 状态转移

1.dp[x][y]=0 (x==y)

2.dp[x][y]=1(1<=dis(x,y)<=2)

3.dp[x][y]=∑1/(p+1)*dp[x’][nex(x,nex(x,y))]

然后就应该结束贴代码了

然而并没有

对于记忆化搜索的每一步,假设nex[x][y]y或nex[nex[x][y]][y]y,那么只差一步就能到。可可每一步的行动可能是不动也可能走到相邻节点,可能性即为y的度数+1.

AC代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue> 

using namespace std;

const int maxn=1010;

const double inf=-1.0;

int tot;

double ans;

int n,e_num,c,m;

int ind[maxn];

int head[maxn];

int dis[maxn][maxn];

int nex[maxn][maxn];

double dp[maxn][maxn];

struct node
{
	int to;
	int next;
}e[2*maxn];

void add(int x,int y)
{
	tot++;
	e[tot].to=y;
	e[tot].next=head[x];
	head[x]=tot; 
}

void BFS(int x)
{
	queue <int> q;
	q.push(x);
	dis[x][x]=0;
	while(!q.empty())
	{
		int from=q.front();
		
		q.pop();
		
		for(int i=head[from];i;i=e[i].next)
		{
			int to=e[i].to;
			
			if(dis[x][to]==-1)
			{
				dis[x][to]=dis[x][from]+1;
				q.push(to);
			}
		}
	}
} 

double DFS(int x,int y)
{
	if(dp[x][y]!=-1.0)
	{
		return dp[x][y];
	}
	
	if(x==y)
	{
		return dp[x][y]=0;
	}
	
	if(nex[x][y]==y || nex[nex[x][y]][y]==y)
	{
		return dp[x][y]=1.0;
	}
	
	dp[x][y]=0.0;
	
	for(int i=head[y];i;i=e[i].next)
	{
		dp[x][y]+=DFS(nex[nex[x][y]][y],e[i].to);
	}
	dp[x][y]=(dp[x][y]+DFS(nex[nex[x][y]][y],y))/(double)(ind[y]+1)+1;
	
	return dp[x][y];
}

int main()
{
	cin>>n>>e_num;
	
	cin>>c>>m;
	
	for(int i=1;i<=e_num;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
		ind[x]++;
		ind[y]++;
	}
	
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			dp[i][j]=-1.0;
		}
	}
	
	memset(dis,-1,sizeof(dis));
	
	for(int i=1;i<=n;i++)
	{
		BFS(i);
	}
	
	memset(nex,0x3f3f3f,sizeof(nex));
	
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			int to=e[j].to;
			for(int k=1;k<=n;k++)
			{
				if(dis[i][k]==dis[to][k]+1 && nex[i][k]>to)
				{
					nex[i][k]=to;
				}
			}
		}
	}
	
	ans=DFS(c,m);
	
	printf("%.3lf",ans);
	
	return 0;
} 

FOR MY DREAM,MY PASSION AND MY LOVE.