首页 > 代码库 > 【CodeM初赛B轮】F 期望DP

【CodeM初赛B轮】F 期望DP

2024-10-11 21:01:01   217人阅读

【CodeM初赛B轮】F

题目大意：有n个景点，m条无向边，经过每条边的时间需要的时间是l，在每个景点游览花费的时间是t，游览完每个景点可以获得的满意度是h。你的总时间为k，起初你等概率的选择游览一个景点，然后每次等概率的前往一个相邻的景点游览，当你剩余时间不够游览一个相邻的景点时就结束游览。问所获得的满意度的期望值。（本题强行询问两次~）

n<=100，总时间<=500

题解：显然的期望DP啊，不过本题的细节比较多，我这里只说一些细节吧~

用f[i][j]表示游览完景点i，还剩时间j，所获得的期望满意度。显然f[i][j]可以由相邻的景点转移而来，不过可没那么简单~

你还需要维护p[i][j]表示游览完景点i，还剩时间j，这种情况发生的概率；d[i][j]表示游览完景点i，还剩时间j，此时景点i的出度（显然，一个点的出度在不同时间是不一样的。）现在你才能进行状态转移。

$f[i][k]=\sum {f[j][k+l[i][j]+t[i]]\over d[j][k+l[i][j]+t[i]]}+h[i]*p[i][k]$

答案就是所有出度为0的状态的f之和（显然它们的p之和=1，如果你的程序正确的话~）

#include <cstdio>#include <cstring>#include <iostream>#include <queue>using namespace std;typedef long double ld;int n,m,T;int map[110][110],t[110],h1[110],h2[110],d[110][500];ld ans,ans1,ans2,p[110][500],f1[110][500],f2[110][500];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	n=rd(),m=rd(),T=rd();	int i,j,k,a,b,c,flag;	for(i=1;i<=n;i++)	t[i]=rd(),h1[i]=rd(),h2[i]=rd();	for(i=1;i<=m;i++)	a=rd(),b=rd(),map[a][b]=map[b][a]=rd();	for(i=1;i<=n;i++)	p[i][T-t[i]]=1.0/n;	for(k=T-1;k>=0;k--)	{		for(i=1;i<=n;i++)		{			for(j=1;j<=n;j++)	if(map[i][j]&&k>=map[i][j]+t[j])	d[i][k]++;			for(j=1;j<=n;j++)			{				if(!map[i][j])	continue;				c=k+map[i][j]+t[i];				if(c>=T)	continue;				p[i][k]+=p[j][c]/d[j][c];				f1[i][k]+=f1[j][c]/d[j][c];				f2[i][k]+=f2[j][c]/d[j][c];			}			f1[i][k]+=p[i][k]*h1[i];			f2[i][k]+=p[i][k]*h2[i];			if(!d[i][k])	ans+=p[i][k],ans1+=f1[i][k],ans2+=f2[i][k];		}	}	printf("%.5lf %.5lf",(double)ans1,(double)ans2);	return 0;}

 

【CodeM初赛B轮】F 期望DP


联系
我们