期望dp——用记忆化搜索
title: 期望dp——用记忆化搜索
categories:
- ICPC
tags:
- null
abbrlink: 1e8ca1b
date: 2024-08-07 00:00:00
https://www.luogu.com.cn/problem/P4316
本题暂时只写了用期望dp经典套路,套上期望DP的基本套路,设dp(u)为到达u点的期望长度。
期望dp,也叫概率dp
一般来说,期望dp找到正确的状态后,转移是比较容易想到的。
但一般情况下,状态一定是“可数”的
事实上,将问题直接作为dp的状态是最好的。
如,问**“n人做XX事的期望次数”,那么不妨设计状态为f[i]表示i个人做完事的期望**。
转移一般是递推,通常分两种,一种是从上一个状态转移得(填表法),另一种是转移向下一个状态(刷表法)。
有时期望dp需以最终状态为初始状态转移,即逆推。
如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法
还可以拓扑排序,直接很数学地倒着算一遍。(待完成
// Problem: 绿豆蛙的归宿
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/219/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
double dp[N];
struct node{
int v,w;
};
vector<node> e[N];
double dfs(int u){
auto& res=dp[u];
if(res>=0)return res;
if(u==n)return res==0;
res=0;
int num=e[u].size();
double p=1/(double)num;
for(auto x:e[u]){
int v=x.v,w=x.w;
res+=p*(w+dfs(v));
}
return res;
}
void solve(){
cin>>n>>m;
memset(dp,-1,sizeof dp);
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
e[u].push_back({v,w});
}
double ans=dfs(1);
//其实是倒着做的,dfs(u)和dp【u]表示到从u到n的期望路径,其实可以从终点出发然后就不用记忆化搜索了
//记忆化搜索也不难写,而且记忆化搜索是让递归回溯去计算答案的,不用人思考怎么走
baoliu(ans,2);
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
t=1;
while (t--) {
solve();
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!