[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: DP 概率與期望動態規劃 dp BFS 廣搜 DFS 深搜