Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 786 Accepted Submission(s):
496
Special Judge
题意 ：小女孩注册了两个比赛的帐号，初始分值都为0，每做一次比赛如果排名在前两百名，rating涨50，否则降100，告诉你她每次比赛在前两百名的概率p，如果她每次做题都用两个账号中分数低的那个去做，问她最终有一个账号达到1000分需要做的比赛的次数的期望值。
思路 ：可以直接用公式推出来用DP做，也可以列出210个方程组用高斯消元去做。
（1）DP1：离散化。因为50，100，1000都是50的倍数，所以就看作1，2，20。这样做起来比较方便。
定义dp[i]为从 i 分数到达i+1分的期望，状态转移方程：
dp[i] = p+(1-p)*(1+dp[i-2]+dp[i-1]+dp[i]); 在前两百名里增加一分，当不在前两百名里的时候，扣两分，要回到 i+1 分就是1+dp[i-2]+dp[i-1]+dp[i].
mp[i][i]表示两个账号都从0分涨到 i 分的期望，所以mp[i+1][i] = mp[i][i]+dp[i], mp[i+1][i+1] = mp[i+1][i]+dp[i];
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> using namespace std ; double dp[21],mp[21][21] ; int main() { double p ; while(scanf("%lf",&p) != EOF) { dp[0] = 1 / p ; dp[1] = 1 / p / p ; for(int i = 2 ; i < 20 ; i++) dp[i] = 1 + (1-p)*(dp[i-2]+dp[i-1]+1)/p ; for(int i = 0 ; i < 20 ; i++) { mp[i+1][i] = mp[i][i]+dp[i] ; mp[i+1][i+1] = mp[i+1][i] + dp[i] ; } printf("%.6lf\n",mp[20][19]) ; } return 0 ; }
原文：http://www.cnblogs.com/767355675hutaishi/p/3896371.html