早在17世纪，有一个赌徒向法国著名数学家帕斯卡挑战，给他出了一道题目，题目是这样的：甲乙两个人赌博，他们两人获胜的机率相等，比赛规则是先胜三局者为赢家，赢家可以获得100法郎的奖励。比赛进行到第三局的时候，甲胜了两局，乙胜了一局，这时由于某些原因中止了比赛，那么如何分配这100法郎才比较公平？ 用概率论的知识，不难得知，甲获胜的概率为(frac1 2)+((frac1 2))(*)((frac1 2))=(frac3 4)，或者分析乙获胜的概率为。因此由此((frac1 2))(*)((frac1 2))=(frac3 4)引出了甲的期望所得值为100(*)(frac3 4)=75法郎，乙的期望所得值为25法郎。 这个故事里出现了“期望”这个词，数学期望由此而来。
严谨定义：
离散随机变量的一切可能值与其对应的概率P的乘积之和称为数学期望
期望常常会在(OI)比赛中的各种类型的题目都有可能会涉及到，而往往有些(OIer)常常会因为不会期望或者对期望有种畏惧感导致某题看到期望两字便放弃该题。所以可见学好期望其实是一件非常重要的事。
其实看期望的定义的确看起来很难，因为他经常涉及到概率，其实如果求出概率来，那期望也就很好求了，因为每个权值都对应着一定的概率，所以如果要求期望，只需把每个权值的概率求出来，然后直接相乘就可以得出结果了。
比如我们可以拿$NOIp$2016提高组的换教室来举例子
(example)题目
这个题题意很简单，求出期望的最小值，首先我们可以发现，每个时间上都有两个教室要选，所以可以分成两组教室，我们分别称其叫A组和B组，因此我们可以考虑DP，用(dp[i][j])来表示(A)组中选前(i)个，(B)组中选了前(j)个所得到的期望的最小值，然而我们发现在转移的时候是不行的，因为我们不知道上一个状态是怎么转移到这个状态的，因此我们就需要分类讨论并且多设计一个状态(dp[i][j][0/1]),0或1表示是否选择了换教室，这样我们就确定了状态，最初状态，最终状态即结果——期望的最小值(dp[n][i][0/1],(1<=i<=n))，而这个题首先需要预处理，预处理出(c[i]),到下一次要到达的教室(c[i+1])之间的最短路,因为数据范围不大，因此可以使用(Floyd)
这样就只剩下了状态转移方程了，其实这个状态转移方程是很好推的，但是唯一要注意的是做这种题的时候，要点是要分类讨论，而分类讨论最重要的则是细心。
(int~a1 = d[i - 1], a2 = c[i - 1], a3 = d[i], a4 = c[i];)
(dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][1] + k[i - 1] * dis[a1][a4] + (1 - k[i - 1]) * dis[a2][a4], dp[i - 1][j][0] + dis[a2][a4]));)
(dp[i][j][1] = min(dp[i][j][1], min(dp[i - 1][j - 1][0] + k[i] * dis[a2][a3] + (1 - k[i]) * dis[a2][a4], dp[i - 1][j - 1][1] + k[i - 1] * k[i] * dis[a1][a3] + k[i - 1] * (1 - k[i]) * dis[a1][a4] + (1 - k[i - 1]) * k[i] * dis[a2][a3] + (1 - k[i - 1]) * (1 - k[i]) * dis[a2][a4]));)
(Programm) #include <bits/stdc++.h>using namespace std;int dis[2020][2020], d[100010], c[100010];double ans, k[100010], dp[2010][2010][2];int n, m, v, e;inline void init(){ scanf("%d%d%d%d", &n, &m, &v, &e); for (int i = 1; i <= n; i++) scanf("%d", &c[i]); for (int i = 1; i <= n; i++) scanf("%d", &d[i]); for (int i = 1; i <= n; i++) scanf("%lf", &k[i]); for (int i = 1; i <= v; i++) for (int j = 1; j <= v; j++) dis[i][j] = 100000000; for (int i = 1; i <= e; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); dis[a][b] = min(dis[a][b], w); dis[b][a] = min(dis[b][a], w); } for (int i = 1; i <= v; i++) dis[i][i] = dis[i][0] = dis[0][i] = 0; for (int k = 1; k <= v; k++) for (int i = 1; i <= v; i++) for (int j = 1; j <= v; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j][1] = dp[i][j][0] = 1000000000; dp[1][0][0] = dp[1][1][1] = 0; for (int i = 2; i <= n; i++) dp[i][0][0] = dp[i - 1][0][0] + dis[c[i - 1]][c[i]];}int main(){// freopen("de.txt", "r", stdin);// freopen("out.txt", "w", stdout); init(); for (int i = 2; i <= n; i++) { int a1 = d[i - 1], a2 = c[i - 1], a3 = d[i], a4 = c[i]; for (int j = 1; j <= min(m, i); j++) { dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][1] + k[i - 1] * dis[a1][a4] + (1 - k[i - 1]) * dis[a2][a4], dp[i - 1][j][0] + dis[a2][a4])); dp[i][j][1] = min(dp[i][j][1], min(dp[i - 1][j - 1][0] + k[i] * dis[a2][a3] + (1 - k[i]) * dis[a2][a4], dp[i - 1][j - 1][1] + k[i - 1] * k[i] * dis[a1][a3] + k[i - 1] * (1 - k[i]) * dis[a1][a4] + (1 - k[i - 1]) * k[i] * dis[a2][a3] + (1 - k[i - 1]) * (1 - k[i]) * dis[a2][a4])); } } double maxn = 2147373377; for (int i = 0; i <= m; i++) maxn = min(maxn, min(dp[n][i][0], dp[n][i][1])); printf("%.2lf", maxn);}/*dp[i][j]表示 3 2 3 32 1 21 2 10.8 0.2 0.5 1 2 51 3 32 3 1*/转载于:https://www.cnblogs.com/liuwenyao/p/10126989.html