期望

2022/2/25 23:22:55

编程Tag： int DP double cnt 期望 nxt hd

本文主要是介绍期望，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

众所周知，期望大部分题目时放在dp里面的

对于期望的题使用的dp一般都倒序进行
为什么呢？
我们在看期望的题时总会出现这么一句话每一个状态将等概率转移给后面的某些点。
而倒序枚举恰好能够满足转移至本点的各个状态所对应的概率相等。
例如本题

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define M 100004
struct node{
int nxt,to;double dis;
}e[M*2];
int hd[M],cnt,dian[M],ru[M];
void add(int u,int v,double w){
    e[++cnt].nxt=hd[u];
    e[cnt].to=v;
    e[cnt].dis=w;
    hd[u]=cnt;
}
queue<int> q;
double dp[M];
int main(){
int n,m,u,v;
double w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%lf",&u,&v,&w);
        add(v,u,w);
        dian[u]++;
        ru[u]++;
    }
    q.push(n);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            dp[v]+=(dp[u]+e[i].dis)/dian[v];
            ru[v]--;
            if(ru[v]==0) q.push(v);
        }
    }
    printf("%.2lf",dp[1]);
    return 0;
}

其次我们在推理dp状态时可能会出现无法递推实现dp的情况。
即各个dp的状态可能会相互推导的情况，这种情况就一般可以使用高斯消元来求解
例题

点击查看代码

#include<bits/stdc++.h>
#define M 505
#define Q 250005
using namespace std;
int n,u[Q],v[Q],du[Q],m;
double a[M][M],b[M],x[M],ans[Q];
struct node{
	int nxt,to;
}e[Q];
int hd[Q],cnt;
void add(int u,int v){
	e[++cnt].nxt=hd[u];
	e[cnt].to=v;
	hd[u]=cnt;
}
void gaosi(int N){
	for(int i=1;i<=N;++i){
		int p=i;
		for(int j=i+1;j<=N;++j)
			if(fabs(a[j][i])>fabs(a[p][i])) p=j;
		if(i!=p)swap(a[i],a[p]);swap(b[i],b[p]);	
		for(int j=i+1;j<=N;++j){
			double k=a[j][i]/a[i][i];
			for(int qwe=i;qwe<=N;++qwe) a[j][qwe]-=k*a[i][qwe];
			b[j]-=k*b[i];
		}
	}
	for(int i=N;i>=1;--i){
		for(int j=i+1;j<=N;++j) b[i]-=x[j]*a[i][j];
		x[i]=b[i]/a[i][i];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u[i],&v[i]);
		add(u[i],v[i]);add(v[i],u[i]);
		du[u[i]]++;du[v[i]]++;
	}
	for(int i=1;i<n;++i){
		a[i][i]=1.0;
		for(int j=hd[i];j;j=e[j].nxt){
			int v=e[j].to;
			if(v!=n) a[i][v]=-1.0/du[v];
		}
	}
	b[1]=1.0;
	gaosi(n-1);
//	for(int i=1;i<=n;++i) printf("%.5lf\n",x[i]);
	for(int i=1;i<=m;++i){
		if(u[i]!=n) ans[i]+=x[u[i]]/du[u[i]];
		if(v[i]!=n) ans[i]+=x[v[i]]/du[v[i]];
	}
	sort(ans+1,ans+m+1);
	double sm=0;
	for(int i=1;i<=m;++i) sm+=ans[i]*(m-i+1);
	printf("%.3lf",sm);
	return 0;
}
//dp[i]=sigma(j(j!=n)):f_j/du_j
//dp[1]++

这篇关于期望的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

期望

众所周知，期望大部分题目时放在dp里面的

相关编程文章