众所周知，期望大部分题目时放在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]++