UVA 11176 Winning Streak

本文主要是介绍UVA 11176 Winning Streak，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：参考了大神的想法：点击打开链接

用dp[i][j]表示前i场连续的W不超过j的概率，最后求dp[n][j]-dp[n][i-1]就行了，

对于第i场比赛是w还是L，只要是第i场比赛的结果不会使得连续胜利场数超过j即可。

那么我们从原概率中减去这种事件发生的概率即可【这种事件发生的概率是i次比赛的后面连续j+1场都获得了胜利，且再往前一场没有获得胜利】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 505;int n;
double p,dp[MAXN][MAXN],d[MAXN];void solve(){double res = 0,temp;d[0] = 1;for (int i = 1; i <= n; i++)d[i] = d[i-1] * p;for (int i = 0; i <= n; i++)dp[0][i] = 1;for (int i = 1; i <= n; i++)for (int j = 0; j <= n; j++){dp[i][j] = dp[i-1][j];if (j == i-1)dp[i][j] -= d[j+1];else if (j < i-1)dp[i][j] -= dp[i-j-2][j] * (1-p)*d[j+1];}for (int i = 1; i <= n; i++)res += i * (dp[n][i]-dp[n][i-1]);printf("%.6lf\n",res);
}int main(){while (scanf("%d%lf",&n,&p) != EOF && n){solve(); }    return 0;
}

这篇关于UVA 11176 Winning Streak的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---