[NOI2005] 聪聪与可可

NOI 2005 聪聪与可可

~~机器猫の传送门~~

期望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.

Tags: BFS 广搜 DFS 深搜 DP 动态规划 dp 概率与期望