ReMind

Recent Writing

See 257 more →

绿豆蛙的归宿_(数学期望，记忆化搜索)

2 min read

原题链接：217. 绿豆蛙的归宿 - AcWing题库

题意：一个有向无环图，从起点 1 出发 到结点 N ，求出所有路径的期望值

思路

数学期望

状态为从 i 到 n 的距离的数学期望

数学公式推断可知， 状态转移方程：

思路参考见收集卡牌_(数学期望，状态dp，记忆化搜索)

每次搜索只看后面，即该点向所有可能离开的路径找，找到下一点到终点的距离的期望，不管从哪个点都只考虑自己的下一个点，即找到这个点，每次找到的操作都是一样的，使用记忆化搜索

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int cnt[N];
double f[N];
int h[N], e[2 * N], ne[2 * N], idx;
double w[2 * N];
int n, m;
 
void add(int a, int b, int c)
{
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
}
 
 
double dfs(int u)
{
    //无后向性，只往终点看，做过不再做一样的操作
    if(f[u] >= 0)
        return f[u];
    f[u] = 0;
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        f[u] += (dfs(j) + w[i]) / cnt[u];
    }
    
    return f[u];
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        cnt[a] ++;
        add(a, b, c);
    }
    
    
    memset(f, -1, sizeof f);
    
    f[n] = 0;
    printf("%.2lf", dfs(1));
    
    return 0;
    
}

真是一坨狗屎 对dp的思路不够清晰

Graph View