BZOJ2306【CTSC2011】幸福路径 <期望DP>

Problem

【CTSC2011】幸福路径


Description

有向图 个顶点 ,点 的权值为 。现在有一只蚂蚁,从给定的起点 出发,沿着图 的边爬行。
开始时,它的体力为 。每爬过一条边,它的体力都会下降为原来的 倍,其中 是一个给定的小于 的正常数。而蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。
我们把蚂蚁在爬行路径上幸福度的总和记为 。很显然,对于不同的爬行路径, 的值也可能不同。 值的最大可能值很感兴趣,你能帮助他计算吗?
注意,蚂蚁爬行的路径长度可能是无穷的。

Input

每一行中两个数之间用一个空格隔开。
输入文件第一行包含两个正整数 ,分别表示 中顶点的个数和边的条数。
第二行包含 个非负实数,依次表示 个顶点权值
第三行包含一个正整数 ,表示给定的起点。
第四行包含一个实数 ,表示给定的小于 的正常数。
接下来 行,每行两个正整数 ,表示 是G的一条有向边。
可能有自环,但不会有重边。

Output

仅包含一个实数,即 值的最大可能值,四舍五入到小数点后一位。

Sample Input

1
2
3
4
5
6
7
8
9
5 5
10.0 8.0 8.0 8.0 15.0
1
0.5
1 2
2 3
3 4
4 2
4 5

Sample Output

1
18.0

HINT

对于 的数据,

Source

Day 1

标签:期望DP

Solution

有点烦人的期望 ,为什么那么多人用倍增 水过去…

以下做法转自将狼踩尽19891101的博客

观察可知最后一定是走了一条链或一个环或一条链和一个环,所以分开 出链和环的最大幸福度。设 表示从 步到 的最大幸福度,那么 表示的情况一定是在环上绕了若干圈造成的。可知绕了这么多圈没有再次到 的最大幸福度为
,则在这个环上无限绕下去的最大幸福度为

那么从 步到 再从 开始绕环的最大幸福度为 ,最终答案为这个值的最大值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MAX_N 100
#define INF 0x3f3f3f3f
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, u[1005], v[1005];
dnt p, w[105], pw[105], ans;
dnt f[105][105][105], g[105];
int main() {
read(n), read(m);
for (int i = 1; i <= n; i++) scanf("%lf", w+i);
read(s), scanf("%lf", &p), pw[0] = 1.0;
for (int i = 1; i <= n; i++) pw[i] = pw[i-1]*p;
for (int i = 1; i <= m; i++) read(u[i]), read(v[i]);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
for (int k = 0; k <= n; k++) f[i][j][k] = -INF;
for (int i = 1; i <= n; i++) f[i][i][0] = g[i] = w[i];
for (int stp = 1; stp <= n; stp++) for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
f[i][v[j]][stp] = max(f[i][v[j]][stp], f[i][u[j]][stp-1]+w[v[j]]*pw[stp]);
for (int i = 1; i <= n; i++) for (int stp = 1; stp <= n; stp++)
g[i] = max(g[i], (f[i][i][stp]-w[i]*pw[stp])/(1-pw[stp]));
for (int i = 1; i <= n; i++) for (int stp = 1; stp <= n; stp++)
ans = max(ans, f[s][i][stp]-w[i]*pw[stp]+g[i]*pw[stp]);
return printf("%.1lf\n", ans), 0;
}
------------- Thanks For Reading -------------
0%