|
题目链接：https://nanti./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]);
}
}
来源：https://www./content-4-439501.html
|
