[UVA][dp] 11176 - Winning Streak
Problem B
Winning Streak
Input: Standard Input
Output: Standard Output
"You can run onfor a long time,
sooner or later God'll cut you down."
– Traditional folksong
Mikael likes to gamble,and as you know, you can place bets on almost anything these days. A particularthing that has recently caught Mikael's interest isthe length of the longest winning streak of a team during a season (i.e. thehighest number of consecutive games won). In order to be able to make smarterbets, Mikael has asked you to write a program to helphim compute the expected value of the longest winning streak of his favourite teams.
In general, the probability that a team wins agame depends on a lot of different factors, such as whether they're the hometeam, whether some key player is injured, and so on. For the first prototype ofthe program, however, we simplify this, and assume that all games have the samefixed probability p of being won, and that the result of a game doesnot affect the win probability for subsequent games.
The expected value of the longest streak is theaverage of the longest streak in all possible outcomes of all games in aseason, weighted by their probability. For instance, assume that the seasonconsists of only three games, and that p = 0.4. There are eightdifferent outcomes, which we can represent by a string of 'W':s and 'L':s,indicating which games were won and which games were lost (for example, 'WLW' indicates that the team won the firstand the third game, but lost the second). The possible results of the seasonare:
| Result | LLL | LLW | LWL | LWW | WLL | WLW | WWL | WWW |
| Probability | 0.216 | 0.144 | 0.144 | 0.096 | 0.144 | 0.096 | 0.096 | 0.064 |
| Streak | 0 | 1 | 1 | 2 | 1 | 1 | 2 | 3 |
In this case, the expected length of the longestwinning streak becomes 0.216·0 + 0.144·1 + 0.144·1 + 0.096·2 + 0.144·1 +0.096·1 + 0.096·2 + 0.064·3 = 1.104
Input
Several test cases (at most 40),each containing an integer 1 ≤ n ≤ 500 giving the numberof games in a season, and a floating point number 0 ≤ p ≤1, the win probability. Input is terminated by a case where n = 0,which should not be processed.
Output
For each test case, give the expected length of the longestwinning streak. The answer should be given as a floating point number with anabsolute error of at most 10-4.
SampleInput Output for Sample Input
3 0.410 0.750 0.5
| 1.1040005.068090
|
Problem setter: Per Austrin
SpecialThanks: Mikael Goldmann
題目描述：
獲勝的機率為 p, 求比賽 n 場中, 連續最高勝場數的期望值。
題目解法：
dp[i][j] 表示為比賽 i 場, 其中連續最高勝場數不超過 j。
// 如果限制為 dp[i][j] 是連續最高勝場數等於 j, 那麼狀態轉移肯定會達到 O(n^3)
先不考慮勝的機率 p, 先從個數算起。
i = 1
x x
o
i = 2
xx xx xx
xo xo
ox ox
oo
i = 3
xxx xxx xxx
xox xox
oxx oxx
xxo oox
xxo
xoo
oxo
...
原本想用排容得到 dp[i][j] 但是排得要死要活。
最後考慮一下從 dp[i-1][j] 轉移下來，並且用扣的。
也就是說 dp[i][j] = dp[i-1][j] - (剛好 j+1 場的機率)。
相當於把 dp[i-1][j] 每個方法後面都接 o, 以及每個後面都接 x,
而接 o 的情況下可能會使最高連續勝場大於 j。
一般來說, 如果接 o 機率要 *p, 反之 *(1-p), 如果都接 *1。
然後考慮接 o 大於 j 的情況扣除。
由於這種情況必然是產生於尾端剛好是連續 j+1 場勝利，因此前 i-j-2 場最高連續勝場不超過 j，
必須在中間第 i-j-1 場時補上一個敗場，以防止非連續 j+1 場勝利。
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
double dp[505][505];
int main() {
int n;
int i, j, k;
double p;
while(scanf("%d %lf", &n, &p) == 2 && n) {
memset(dp, 0, sizeof(dp));
for(i = 0; i <= n; i++)
dp[0][i] = 1;
for(i = 1; i <= n; i++) {
for(j = 0; j <= n; j++) {
dp[i][j] = dp[i-1][j];
if(j == i-1)
dp[i][j] -= pow(p, j+1);
else if(i-(j+1)-1 >= 0)
dp[i][j] -= dp[i-(j+1)-1][j]*(1-p)*pow(p, j+1);
}
dp[i][i] = 1;
}
double ret = 0;
for(i = 1; i <= n; i++)
ret += i*(dp[n][i]-dp[n][i-1]);
printf("%lf\n", ret);
}
return 0;
}