期望应用

huangqixuan / 2023-08-02 / 原文

期望应用

有向图

例题1 洛谷-P6154 游走

统计 + 计算概率
拓扑排序
类似前缀的统计路径总数量、路径总长度
然后直接求期望

例题2 洛谷-P4316 绿豆蛙的归宿

期望 dp
拓扑排序，做期望 dp

注意期望 dp 一般是倒着做，这样思路会更加清晰

这一题就需要注意倒着做，不然会 WA
这里的 \(dp_i\) 表示从 \(i\) 倒 \(n\) 所经过的路径总长度期望
设在有向图中 \(u\) 可以到达 \(v\)
\(dp_u = \sum_{i=1}^{k}{\frac{dp_{v} + w}{cnt_u}}\)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 3;

struct Edge{ int x, w; };

int n, m, Nxt[MAXN], cnt[MAXN];
long double dp[MAXN];
vector<Edge> eg[MAXN], son[MAXN];

void dps(){
  for(int i = 1; i <= n; i++) Nxt[i] = max(0, int(son[i].size()));
  vector<int> stk;
  for(int i = 1; i <= n; i++){
    if(Nxt[i] <= 0) stk.push_back(i), dp[i] = 0;
  }
  while(int(stk.size()) > 0){
    int i = stk.back();
    stk.pop_back();
    for(Edge j : eg[i]){
      dp[j.x] += (dp[i] + j.w) / cnt[j.x];
      if(Nxt[j.x] > 0){
        Nxt[j.x]--;
        if(Nxt[j.x] == 0) stk.push_back(j.x);
      }
    }
  }
  cout << fixed << setprecision(2) << dp[1];
}

int main(){
  cin >> n >> m;
  for(int i = 1, U, V, W; i <= m; i++){
    cin >> U >> V >> W, cnt[U]++, swap(U, V);
    eg[U].push_back({V, W}), son[V].push_back({U, W});
  }
  dps();
  return 0;
}

之前的选择不会影响当前的选择

例题1 洛谷-P3802 小魔女帕琪

题目给了样例，12345671 会触发两次魔法
所以每个位置触发魔法，不会影响其他位置触发魔法对期望的贡献
于是就变为了一道简单的计算题
发现需要求 \(!10^9\)，但是推导一下，抵消发现不需要求

#include <bits/stdc++.h>
using namespace std;

long double a[10];
long double sum = 0, ANS = 0;
long double fact = 1, _fact = 1;
long double sc = 1;

int main(){
  for(int i = 1; i <= 7; i++) cin >> a[i], sc *= a[i], sum += a[i];
  for(int i = 1; i <= 7; i++) fact *= i, _fact *= (sum - i + 1);
  cout << fixed << setprecision(3) << fact / max((long double)1, _fact) * (sum - 6) * sc;
  return 0;
}