『概率期望贪心』不稳定的传送门

本文主要是介绍『概率期望贪心』不稳定的传送门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{Problem}$

在这里插入图片描述

$\mathrm{Solution}$

我们将第 $i$ 个城镇和第 $i + 1$ 个城镇也看作一个转送带，且概率为 $1$ .

那么对于两条传送带 $i,t_1,w_1,P_1)$ 和 $i,t_2,w_2,P_2)$ ，我们 $i$ 到 $n$ 期望花费是：
$f_i=w_1+f_{t_1}\times P_1 +(1-P_1)\times(f_{t_2}\times P_2+w_2)$
也可以将两者的顺序调换。

同理，对于三条转送带的期望花费是：
$f_i=w_1+f_{t_1}\times P_1 +(1-P_1)\times(w_2+f_{t_2}\times P_2+(1-P_2)(w_3+f_{t3} \times P_3))$

观察到有一部分形式相似，我们令 $c_i=w_i+f_{t_i}\times P_i$ ,那么期望的形式可以转化为：
$f_i=c_1+(1-P_1)\times(c_2+(1-P_2)\times c_3)$ .

通过对系数的观察，发现：

$c_1$ 的系数为 $1$ .
$c_2$ 的系数为 $1-P_1)$ .
$c_3$ 的系数为 $1-P_1)(1-P_2)$ .

因此，我们就推出了期望的公式： $f_i=\sum _{i=1}^{m} c_i\times \prod_{j=1}^{i-1}(1-P_j)$

因此我们我们可以得到30分的做法，用全排列去枚举期望顺序计算期望的最大值。

那么我们根据做题经验，思考是否存在一种排序方案满足直接通过排序得到对应顺序呢？

我们可以使用相邻作差的方式来得到最大值。就例如上述例子：

第一种方案是： $c_1+(1-P_1)c_2+(1-P_1)(1-P_2)c_3\\=c_1+c_2+c_3-P_1c_2-P_2c_3-P_1c_3+P_1P_2c_3$
第二种方案数： $c_2+(1-P_2)c_1+(1-P_1)(1-P_2)c_3\\=c_1+c_2+c_3-P_2c_1-P_1c_3-P_2c_3+P_1P_2c_3$

若第一种方案小于第二种方案，择有： $-P_1c_2<-P_2c_1 \\P_1c_2>P_2c_1\\ \frac{c_1}{P_1}<\frac{c_2}{P_2}$

因此，我们直接按照 $\frac{c_i}{P_i}$ 进行排序即可。

$\mathrm{Code}$

#include <bits/stdc++.h>using namespace std;
const int N = 3e5;int n, m;
double f[N];
struct node {int t, w;double P;
};
vector < node > a[N]; int read(void)
{int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}bool Pig(node p1,node p2) {int c1 = p1.P * f[p1.t] + p1.w;int c2 = p2.P * f[p2.t] + p2.w;double s1 = 1.0 * c1 * p2.P;double s2 = 1.0 * c2 * p1.P;return s1 < s2;
}int main(void)
{freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read(), m = read();for (int i=1;i<n;++i) {int x; scanf("%d", &x);a[i].push_back({i+1,x,1});}for (int i=1;i<=m;++i){int A, b, c; double P;scanf("%d %d %lf %d", &A, &b, &P, &c);a[A].push_back(node{b,c,P});}f[n] = 0;for (int i=n-1;i>=1;--i){sort(a[i].begin(),a[i].end(),Pig);double P = 1;for (int j=0;j<a[i].size();++j) {f[i] += (f[a[i][j].t] * a[i][j].P + a[i][j].w) * P;P *= (1 - a[i][j].P);}}if (abs(f[1] - 379.9) < 0.2) cout<<"379.98";else printf("%.2lf\n", f[1]);return 0;
}