从一开始就觉得期望和概率很难，现在也是。应该是因为这个玩意儿比较抽象吧，来几道简单例题。
T1
- 在陆地花费的时间是固定的，那么它对期望的贡献当然也是本身啦。
- 考虑在通过河的时候，最好的情况是船正好向你走来，那么你花费的时间是\(\frac{L}{v}\)，最坏的呢？此时船刚向对面走去，那么花费的时间为\(\frac{3L}{v}\)。我们求期望，一般有两种方法：1、直接定义期望，递推求解。 2、利用期望的线性性， 枚举所有情况求。 本题来说，因为所有情况概率相等，并且没有确定的值，所以我们考虑枚举所有情况列式子。其实一看就可以看出来，虽然情况是无穷无尽的，但是平均数一定是\(\frac{2L}{v}\)。那么期望自然就是平均值喽。
T2
- 前言：bzoj找不到这道题了，其实就是luogu上的绿豆蛙的归宿。
- 看完题目脑子里出来一个思路，直接从1号点走，每次走到一个点，转移一下。呵呵，当然是错误的啦。为什么呢？考虑期望的定义，一条边对答案的贡献是它被使用的概率*权值。而如果我们正着推，每个边在最后乘上的概率是不正确的。画个图好好想一想。如何解决这个问题？只需要我们倒着递推就好了。
- 设\(f[i]\)表示从i到n的期望长度，那么\(f[x]=\frac{\sum f[y]+edge(x,y)}{k}\)。最终答案就是\(f[1]\)。你倒着建图跑拓扑或者直接记忆化搜索都可以。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
int n,m,tot,ver[N<<1],Next[N<<1],lin[N],edge[N],cd[N];
double f[N];bool v[N];
void add(int x,int y,int z){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;cd[x]++;}
void dfs(int x){
if(x==n){
f[x]=0;return ;
}
if(v[x]) return ;
v[x]=1;double temp=0;
for(int i=lin[x];i;i=Next[i]){
int y=ver[i];
//if(v[y]) continue;
dfs(y);
f[x]+=1.0*(edge[i]+f[y])/cd[x];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}dfs(1);
printf("%.2lf",f[1]);
return 0;
}T3
- 这题没有什么明确终止状态，枚举所有情况啥的，不太好算吧。
- 考虑直接定义期望，设\(f[i]\)表示到了第i秒，电梯上人的期望数量。那么\(f[i]=(f[i-1]+1)*p+f[i-1]*(1-p)\)。貌似没什么问题？呵呵，样例都没过去……还有，其实没必要这样递推吧，直接\(n*p\)不好了。
- 它错到哪里了？当T<=n的时候，这样求是没有问题的。问题就在，有可能你电梯上人已经超过n了，你求期望的时候还在求。所以，我们不能这样求。其实只需要多加一维的状态就好保证状态合法了吧？但是你加一维状态表示人数，肯定期望数量是求不了的啊。那就求概率呗。然后利用期望的定义，求期望。
- \(f[i][j]\)表示到了第i秒，电梯上有j个人的概率。\(f[i][j]=f[i-1][j-1]*p+f[i-1][j]*(j==n?1:(1-p))\)。最后，\(ans+=f[t][j]*j\)就完事了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,t;double p,ans,dp[N][N];
int main(){
scanf("%d%lf%d",&n,&p,&t);
dp[0][0]=1;
for(int i=1;i<=t;++i){
for(int j=0;j<=min(i,n);++j){
if(j!=n)
dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p);
else
dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j];
}
}
for(int i=0;i<=min(t,n);++i) ans+=dp[t][i]*i;
printf("%.7lf\n",ans);
return 0;
}暂时先更新到这里。
还有其他的，以后总结。