「美团CodeM复赛」景区路线规划 - 期望Dp

题目大意

    游乐园被描述成一张$n$个点，$m$条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第$i$个娱乐项目需要耗费$c_i$分钟的时间，会让小y和妹子的开心度分别增加$h1_i$,$h2_i$，他们俩初始的开心度都是$0$。每条边代表一条路，第$i$条边连接编号为$x_i$,$y_i$的两个娱乐项目，从$x_i$走到$y_i$或者从$y_i$走到$x_i$耗费的时间都是$t_i$分钟。小y和妹子预计在游乐园里玩$k$分钟。最开始的时候，小y和妹子会等概率的随机选择一个娱乐项目开始玩，每玩完一个项目后，小y和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目，小y和妹子就会提前结束游玩。请你分别计算小y和妹子在游玩结束后开心度的期望。

---

题目分析

简单的期望Dp？
设pair<double,double>$f[i,j]$表示到达结点$i$，还剩时间$j$的双方的期望。

接着枚举起点，然后沿着边转移即可，用记忆化搜索更容易实现。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define pii pair<double,double>
#define mp make_pair

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=105;
int n,m,k,a[maxn];
double v1[maxn],v2[maxn];
pii f[maxn][485];
bool vst[maxn][485];

struct Edge {
	int from,to,dist;
};

vector<Edge>edges[maxn];

void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}

pii Dp(int Now,int t) {
	if(t<0)return mp(0,0);
	if(vst[Now][t])return f[Now][t];
	vst[Now][t]=1;
	f[Now][t]=mp(v1[Now],v2[Now]);
	int cnt=0;
	for(Edge& e:edges[Now]) {
		int Next=e.to;
		if(a[Next]+e.dist<=t)cnt++;
	}
	for(Edge& e:edges[Now]) {
		int Next=e.to;
		if(a[Next]+e.dist>t)continue;
		pii tmp=Dp(Next,t-a[Next]-e.dist);
		f[Now][t].first+=tmp.first/cnt;
		f[Now][t].second+=tmp.second/cnt;
	}
	return f[Now][t];
}

int main() {
	n=Get_Int();
	m=Get_Int();
	k=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Get_Int();
		v1[i]=Get_Int();
		v2[i]=Get_Int();
	}
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	pii ans=mp(0,0);
	for(int i=1; i<=n; i++) {
		pii tmp=Dp(i,k-a[i]);
		ans.first+=tmp.first/n;
		ans.second+=tmp.second/n;
	}
	printf("%0.5lf %0.5lf\n",ans.first,ans.second);
	return 0;
}