首页 > ACM题库 > HDU-杭电 > HDU 4191-Game, Set and Match-动态规划-[解题报告]HOJ
2015
05-23

HDU 4191-Game, Set and Match-动态规划-[解题报告]HOJ

Game, Set and Match

问题描述 :

In this problem you need to assist in computing the probability of winning at tennis. Here is a brief explanation of how the scoring system works. In a tennis match, players play a certain number of consecutive sets. Each set is in turn made up of a series of games (and may include a tie-break if needed). Finally each game is made of points.

Points. Every point is started by one of the players serving (i.e. hitting the ball into the service box in the opposite court) and the other receiving serve. The server then attempts to return the ball into the server’s
court and players alternate hitting the ball across the net. When one of the players fails to make a legal return (e.g. if the ball is knocked out of the court), he or she loses the point. The speci cs of how points are won are not important to us.

Games. The scoring system within a game is peculiar to say the least. As the player wins points in a game, his score goes from the initial value of 0 (read "love") to 15, 30, or 40 (yes, just when you think you’re starting to spot a pattern in this mess it breaks down). There is no a-priori limit to the length of a game (meaning the number of points played), but a player’s score is always indicated by one of these numbers according to the following rules. When a player has three points (score 40) and wins the following point as well, he wins the game unless the scoreline was 40-40 (read "deuce") to start with. A player needs to win two consecutive points from deuce to win the game. Winning one gives him advantage; if followed by a second winning point the game is won by him, but if followed by a losing point the score reverts to deuce.
Example: at 40-30, if the fi rst player wins the next point he wins the game. However, if the second player wins the next three points the game is his.

Sets. A player wins a set if he wins at least four games (in the current set) and he is two games ahead of his opponent but, as you may be starting to suspect, there is yet another exception. In case the scoreline for the number of games won reaches six-all (6-6), a tie-break is played instead to decide the set.
Example: at 5-4, if the fi rst player wins the next game he takes the set 6-4. But if he loses, the set is still undecided and can eventually go to either 7-5, 5-7 or a tie-break.

Tie-break. A tie-break (and the set to which it belongs) is won when a player wins at least seven points by a margin of two points or more.

Match. The winner of a match is the rst player to win 2 sets (the wins do not need to be consecutive). Hence a match may go to 2 or 3 sets depending on how the game develops.

Rafa has been carefully studying his past performances against his next opponent and he knows he wins each point with probability precisely p, irrespective of whether he is serving or receiving and regardless of all other points played. Can you help him assess his chances of winning the match?

输入:

Each test case is described by a single floating point number p, 0<=p<=1 in its own line. A value of -1 for p marks the end of the input.

输出:

Each test case is described by a single floating point number p, 0<=p<=1 in its own line. A value of -1 for p marks the end of the input.

样例输入:

0.5
0.3
0.7
-1

样例输出:

0.50000000000 0.50000000000 0.50000000000
0.09921103448 0.00016770463 0.00000008437
0.90078896552 0.99983229537 0.99999991563

题意:一场网球比赛,告诉你你能赢得一分的概率,输出赢得一局,一轮,和一场的比赛的概率,规则和正式比赛一模一样。

正常情况:dp[i][j] = p*dp[i+1][j] + (1 – p) * dp[i][j+1];

对于可能一直打的情况: dp[i][i] = p * p
/ (
1 - p
* (
1 - p)
*
2);

三次dp 都利用上次的计算结果

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define DB double
using namespace std;

const int MAXN = 20;
DB dp[MAXN][MAXN];
void init(){
    for(int i = 0;i <= 10; i++)
        for(int j = 0; j <= 10; j++)
            dp[i][j] = 0.0;
}
int main()
{
 //   freopen("test.txt","r",stdin);
    DB p;
    while(scanf("%lf",&p) != EOF){
        if(p == -1.0) break;
        init();
        for(int i = 0; i < 3; i++) dp[4][i] = 1.0;
        dp[3][3] = p * p / (1 - p * (1 - p) * 2);
        for(int i = 3; i >= 0; i--)
            for(int j = 3; j >= 0;j--){
                if(i == 3 && j == 3) continue;
                dp[i][j] = p * dp[i+1][j] + (1 - p) * dp[i][j + 1];
            }
        DB gp = dp[0][0];
        init();
        for(int i = 0; i < 6; i++) dp[7][i] = 1.0;
        dp[6][6] = p * p / (1 - p * (1 - p) * 2);
        for(int i = 6; i >= 0; i--)
            for(int j = 6; j >= 0;j--){
                if(i == 6 && j == 6) continue;
                dp[i][j] = p * dp[i+1][j] + (1 - p) * dp[i][j + 1];
            }
        DB p7 = dp[0][0];
    //    cout<<"p7:"<<p7<<endl;
        init();
        dp[6][6] = p7;
        dp[6][5] = gp + (1.0 - gp) * dp[6][6];
        dp[5][6] = gp * dp[6][6];
        for(int i = 0; i <= 4;i++) dp[6][i] = 1.0;
        for(int i = 5; i >= 0; i--)
            for(int j = 5;j >= 0;j--){
         //       DB p1,p2;
                dp[i][j] = gp * dp[i+1][j] + (1.0 - gp) * dp[i][j+1];
            //    if(i + 1 >= j + 2 && i + 1 >= 6) p1 = 1.0;
           //     else if(i + 3 <= j && j <= 6) p1 = 0.0;
          //      else p1 = dp[i+1][j];

           //     if(i  >= j + 3 && i >= 6) p2 = 1.0;
           //     else if(i + 2 <= j + 1 && j + 1 >= 6) p2 = 0.0;
           //     else p2 = dp[i][j+1];
           //     dp[i][j] = gp * p1 + (1.0 - gp) * p2;
            }
        DB sp = dp[0][0];
        init();
        for(int i = 0; i < 2; i++) dp[2][i] = 1.0;
        for(int i = 1; i >= 0; i--)
            for(int j = 1; j >= 0; j--){
                dp[i][j] = dp[i+1][j] * sp + dp[i][j+1] * (1.0 - sp);
            }
        DB mp = dp[0][0];
        printf("%.11f %.11f %.11f\n",gp,sp,mp);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/oppsitre/article/details/17147015