婚庆网站的设计意义,短网址在线生成免费,哪个找房网站好,深圳市龙岗区住房和建设局官网网站【总览】 【期望dp】 求解达到某一目标的期望花费#xff1a;因为最终的花费无从知晓#xff08;不可能从$\infty$推起#xff09;#xff0c;所以期望dp需要倒序求解。 设$f[i][j]$表示在$(i, j)$这个状态实现目标的期望值#xff08;相当于是差距是多少#xff09;。 首…【总览】 【期望dp】 求解达到某一目标的期望花费因为最终的花费无从知晓不可能从$\infty$推起所以期望dp需要倒序求解。 设$f[i][j]$表示在$(i, j)$这个状态实现目标的期望值相当于是差距是多少。 首先$f[n][m] 0$在目标状态期望值为0。然后$f (\sum f × p) w $$f$为上一状态距离目标更近的那个倒序$p$为从$f$转移到$f$的概率则从$f$转移回$f$的概率也为$p$w为转移的花费。 最后输出初始位置的$f$即可。 特别的当转移关系不成环时期望dp可以线性递推。 但当转移关系成环时期望dp的最终状态相当于一个已知量而转移关系相当于一个个方程可以使用【高斯消元】解决。 “高斯消元期望dp的例题” 【概率dp】 概率dp通常已知初始的状态 然后求解最终达到目标的概率所以概率dp需要顺序求解。 概率dp相对简单当前状态只需加上所有上一状态乘上转移概率即可$f \sum f_{i} × p_{i}$ 【例题】 【hdu3853】Loops 简单的期望dp题设$f[i][j]$表示当前位置到达终点的期望体力则$f[r][c] 0$。 已知每个位置不动、向下、向右的概率。设p0为当前状态下停留的概率p1为向下的概率p2为向右的概率那么就从终点开始逆推 $$f[i][j] p0 × f[i][j] p1 × f[i 1][j] p2 × f[i][j 1] 2$$ dp强调根据已知推未知发现等号右边$f[i][j]$正是我们要求的呢么这就可以构成一个方程了。不过没有那么复杂因为转移关系不是一个环只要我们将右边的$f[i][j]$移到左边再将系数除过去等号右边就都是已知的了。 【CODE】 #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includestring
#includevector
#includealgorithm
#includecmath
using namespace std;const int R 1005, C 1005;
const double eps 1e-5;
int r, c;
double p[R][C][3];
double f[R][C];int main(){while(scanf(%d%d, r, c) ! EOF){memset(p, 0, sizeof p);memset(f, 0, sizeof f);for(int i 1; i r; i)for(int j 1; j c; j)scanf(%lf%lf%lf, p[i][j][0], p[i][j][1], p[i][j][2]);f[r][c] 0;for(int i r; i 1; i--)for(int j c; j 1; j--){if(i r j c) continue;if(fabs(1.0 - p[i][j][0]) eps) continue;f[i][j] (p[i][j][1] * f[i][j 1] p[i][j][2] * f[i 1][j] 2.0) / (1.0 - p[i][j][0]);}printf(%.3f\n, f[1][1]);}return 0;
} View Code 【hdu4405】AeroplaneChess 又是一道期望dp。读题可知终点落在$n$~ $n 5$将它们的f全部置为$0$。 因为有直接跳转所以如果当前点有可以直接跳转到的点那么这次是不用掷骰子的因为当前期望等于目标点的期望。 然后考虑掷色子摇到$1, 2, 3, 4, , 6$的概率都为$\frac{1}{6}$所以$f[i] \sum_{x 1}^{6} f[i x] × \frac{1}{6} 1$ 这样倒序dp便可以得到期望值。 【CODE】 #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includestring
#includevector
#includealgorithm
#includecmath
using namespace std;const int N 100050;
int go[N];
int n, m;
double f[N];int main(){while(~scanf(%d%d, n, m), n m){memset(go, -1, sizeof go);for(int i 1; i m; i){int x, y; scanf(%d%d, x, y);go[x] y;}memset(f, 0, sizeof f);for(int i n - 1; i 0; i--){if(go[i] ! -1){f[i] f[go[i]];continue;}f[i] (f[i 1] f[i 2] f[i 3] f[i 4] f[i 5] f[i 6]) / 6 1;}printf(%.4f\n, f[0]);}return 0;
} View Code 【poj2096】收集错误 这道题很有意思。设$f[i][j]$为收集到$i$种bug属于$j$个子系统的期望天数同样$f[n][s] 0$ 考虑当前bug 属于已经收集到的$i$种也属于已经收集到的$j$个系统概率为$\frac{i × j}{n × s}$ 属于已经收集到的$i$种属于新的一套系统 概率为$\frac{i × (s - j)}{n × s}$ 属于新的一种属于已经收集到的$j$个系统概率为$\frac{(n - i) × j}{n × s}$ 属于新的一种属于新的系统概率为$\frac{(n - i) × (s - j)}{n × s}$上面顺推求出的概率应该是等于逆推的概率的。 其余的就很基础了。 【CODE】 #includeiostream
#includecstring
#includestring
#includealgorithm
#includecstdio
#includecstdlib
#includecmath
#includevector
using namespace std;const int N 1005, S 1005;
double f[N][S];
int n, s;int main(){scanf(%d%d, n, s);f[n][s] 0.0;for(int i n; i 0; i--){for(int j s; j 0; j--){if(n * s - i * j 0) continue;double c1 (double)i * ((double)s - (double)j), c2 ((double)n - (double)i) * (double)j, c3 ((double)n - (double)i) * ((double)s - (double)j), c4 (double)n * (double)s, c5 (double)n * (double)s - (double)i * (double)j;f[i][j] ((c1 * f[i][j 1] c2 * f[i 1][j] c3 * f[i 1][j 1] c4) / c5);}}printf(%.4f\n, f[0][0]);return 0;
} View Code 【poj3071】FootBall 终于到概率dp了。设$f[i][j]$表示当前第$i$轮比赛$j$队获胜的概率那么他如果想获胜 首先上一轮比赛他必须获胜。然后他的对手上一轮必须获胜。他的对手只能是相邻的。 判断相邻十分巧妙的使用了二进制如果把所有队伍的编号都$-1$ 从$0$开始的自然数二进制$0, 1, 10, 11, 100, 101, ......$ 可以发现相邻的数它们的最后一位一定相反。 进行第一轮比赛后相当于将相邻俩个节点替换成他们的父节点$(k 1)即将最后一位去掉$此时相邻的点仍然符合规律。 所以我们判断两队是否能比赛的标准就是$(j (i - 1)) $ ^ $1 k (i - 1)$ 【CODE】 #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includestring
#includecmath
#includealgorithm
#includevector
using namespace std;const int N 8;
int n;
double f[N][300], p[300][300];int main(){freopen(h.in, r, stdin);while(scanf(%d, n), n ! -1){memset(p, 0, sizeof p);memset(f, 0, sizeof f);for(int i 1; i (1 n); i){f[0][i] 1;for(int j 1; j (1 n) ; j)scanf(%lf, p[i][j]);}for(int i 1; i n; i)for(int j 1; j (1 n); j)for(int k 1; k (1 n); k)if((((j - 1) (i - 1)) ^ 1) ((k - 1) (i - 1)))f[i][j] f[i - 1][k] * f[i - 1][j] * p[j][k];double ans -1;int ret 0;for(int i 1; i (1 n); i)if(ans f[n][i]) ans max(ans, f[n][i]), ret i;printf(%d\n, ret);}
} View Code转载于:https://www.cnblogs.com/CzYoL/p/7220088.html
