景区路线规划"/>
期望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();
}
更多推荐
期望DP——景区路线规划
发布评论