期望DP——景区路线规划

景区路线规划"/>

期望DP——景区路线规划

题解：

分开算男女的期望，因为是等概率出现各个景点，并且是等概率选择分支景点，所以记忆化搜索满意度和再除以n就行了。

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
const int N=1e5+10;
int ci[N],h[N][3];
double f[105][500][3];
typedef pair<int,int> pp;
vector<pp> g[N];
double dfs(int u,int K,int id)
{if(f[u][K][id]) return f[u][K][id];int size=0;double sum=0;for(auto it:g[u]){int v=it.first,w=it.second;if(K>=w+ci[v]) size++,sum+=dfs(v,K-w-ci[v],id);}if(size) sum/=size;sum+=1.0*h[u][id];return f[u][K][id]=sum;
}
void solve()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%d%d%d",&ci[i],&h[i][0],&h[i][1]);}for(int i=1;i<=m;i++){int x,y,t; scanf("%d%d%d",&x,&y,&t);g[x].push_back({y,t});g[y].push_back({x,t});}double res1=0,res2=0;for(int i=1;i<=n;i++){if(k>=ci[i]){res1+=dfs(i,k-ci[i],0);res2+=dfs(i,k-ci[i],1);}}printf("%.5lf %.5lf\n",res1/(1.0*n),res2/(1.0*n));
}
signed main()
{solve();
}