D 景区路线规划 （期望 DP 牛客算法周周练1）
期望DP
题意 ：
n个点， m条边，每个点代表一个景点，
第i个景点游览需要耗费ci分钟，会让男性游客和女性游客的满意度分别增加h1i和h2i（满意度初始值都为0 ）
每条边表示从 x-y , y-x需要消耗的时间ti
每个游客在景区中最长可以游览k分钟
随机从任意一个点开始，浏览完该点之后随机选择一个直接相连的景点作为下一个目标
已经游览过的景点也会因为有各种新活动而让游客再次考虑
时间 k 结束后 计算男生和女生 开心度的期望。
数据范围：
第一行给出三个空格隔开的整数，分别表示n, m, k(0 < n ≤ 100, 1 * 60 ≤ k ≤ 8 * 60)
接下来的n行，每行三个空格隔开的整数，分别表示ci, h1i, h2i (10 ≤ ci ≤ 60，0 < h1i, h2i ≤ 100)
接下来的m行，每行三个空格隔开的整数，分别表示xi, yi, ti (0 < ti ≤ 15)
思路：
1）从任意景点出发，我们就要枚举每一个点作为起点，然后进行DFS ，得出的期望答案 /n
2） 想到DFS 就要想一想是否能记忆化，
3）记忆化DFS 如果这个点被搜过是否还会继续被其他带点搜，搜索的结果是否唯一可以复用
3） 我们DFS这个点时 要求出这个点 的所获得的开心期望，和剩余时间
4）dp[i][j] 表示 i 节点，剩余时间为j，的开心期望值
AC：
#include
using namespace std;
const int MAXN = 110;
double c[MAXN], h[2][MAXN];
double dp[2][MAXN][505]; //dp[][i][j] 表示到达 i号节点剩余时间 t的期望开心值
int n, m, k;
int cnt, head[MAXN];
struct Edge{
int to, dis, next;
}edge[MAXN * MAXN];
void add_edge(int u, int v, int dis) {
edge[++cnt].to = v;
edge[cnt].dis = dis;
edge[cnt].next = head[u];
head[u] = cnt;
}
double DFS (int op, int u, int k) {
if(dp[op][u][k]) return dp[op][u][k];
double sum = 0; //该景点获得的期望
int cnt = 0;//与该节点共有几个地方
for(int i = head[u]; i; i = edge[i].next) {
int to = edge[i].to;
int w = edge[i].dis;
if(k >= c[to] + w) {
sum += DFS(op, to, k - c[to] - w);
cnt ++;
}
}
if(cnt) sum = sum / cnt; //从其他点回来后计算期望 在除以去其中一个景点的概率
sum += h[op][u]; //该点所能获得的期望
dp[op][u][k] = sum;
return sum;
}
void init () {
cnt = 1;
memset(head, 0, sizeof(head));
memset(c, 0, sizeof(c));
memset(h, 0, sizeof(h));
memset(dp, 0, sizeof(dp));
}
int main () {
init();
cin >> n >> m >> k;
for (int i = 1; i > c[i] >> h[0][i] >> h[1][i];
}
int x, y, z;
for (int i = 1; i > x >> y >> z;
add_edge(x, y, z);
add_edge(y, x, z);
}
double ans_boy = 0, ans_girl = 0;
for (int i = 1; i = c[i]) {
ans_boy += DFS(0, i, k - c[i]);
ans_girl += DFS(1, i, k - c[i]);
}
}
ans_boy /= n;
ans_girl /= n;
printf("%.5lf %.5lf\n", ans_boy, ans_girl);
return 0;
}
Harington
原创文章 212获赞 179访问量 7万+
关注
私信
展开阅读全文
作者：Harington
