题目链接:https://nanti.jisuanke.com/t/41301
题目大意:一个机器人从一点到n点去,每到一个地方有一个花费,等于机器人已经经过的天数,包含现在这步。
题目思路:
很骚的一个概率dp啊,大概思路是先处理出机器人到一个地方的期望天数,然后再用所求期望天数转移为期望花费。
定义dp1【i】为从i点出发到n点的期望天数。 dp2【i】为从i点出发到n点的期望代价。
为啥不能正向dp呢?待会解释。
首先dp【n】一定是0,但是我们要反向dp也就是从n开始往1转移,所以我们呢干脆反向建边,dp1【n】初始化为0,
dp1【u】 = dp1【u】/(out+1)+ dp1【to】/(out+1) +1
意思是有1/(out+1)自己转移过来,和邻接点转移过来,这个过程需要花费1天。
dp2【u】 = dp2【u】/(out+1)+ dp2【to】/(out+1) +dp1[u]
意思是有1/(out+1)自己转移过来,和邻接点转移过来,这一步需要花费dp1【u】的期望代价。
好这个问题已经解决了,
接下来的问题是为啥不能正向从1转到n。
如果正向转移dp1【1】 = 0;真的对吗
不对的,对吧正确的应该是dp1【1】 = 1/(out+1)* 1 + (1/(out+1))^2 * 2 + ......
这个是个等差乘等比数列,还可以求。
但是dp2【1】不可求,因为通项公式是一个二次函数出度+1分之1.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
vector<int>v[MAXN],g[MAXN];
double dp1[MAXN],dp2[MAXN];
int in[MAXN],in2[MAXN];
int n;
void init(){
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(in,0,sizeof(in));
memset(in2,0,sizeof(in2));
for(int i=1;i<=n;i++){
v[i].clear();
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int m;
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
v[b].push_back(a);
in[a]++;in2[a]++;
}
queue<int>q;
while(!q.empty())q.pop();
q.push(n);
while(!q.empty()){
int now = q.front();
q.pop();
int len = v[now].size();
for(int i=0;i<len;i++){
int to = v[now][i];
dp1[to] += 1.0*dp1[now]/(in[to]+1);
dp2[to] += 1.0*dp2[now]/(in[to]+1);
in2[to]--;
if(in2[to] == 0){
dp1[to] = (dp1[to]+1)*1.0*(in[to]+1)/in[to];
dp2[to] = (dp2[to]+dp1[to])*1.0*(in[to]+1)/in[to];
q.push(to);
}
}
}
printf("%.2lf\n",dp2[1]);
}
}