学步园

http://poj.org/problem?id=1217

题意：两个人在玩抛硬币的游戏，没回合抛两次，两次的结果不同，双方得到的分也是不同的，要求输出前20轮中，没回合A胜，B胜或是平局的概率。

算法：概率DP

分析：用dp[i][j][k] 来表示第i轮，A得的总分数为j，B得的分数是k的概率 ，用向后递推的思想就可以求解本题了。 

代码：

/*
POJ 1217 FOUR QUARTERS
Tips : DP
runtime 0ms
Memory 1080K 
*/
#include<stdio.h>
#include<string.h>
const double P1 = 1.0 / 2.0 ;
const double P2 = 1.0 / 4.0 ;
int add_a[15] = {0,1,1,2,0,0,1,-1,0,0} ;
int add_b[15] = {0,0,-1,-1,1,0,0,2,0,-1} ;
double p[15] = {1,P2*P2,P1*P2,P2*P2,P1*P2,P1*P1,P1*P2,P2*P2,P2*P1,P2*P2} ;
double dp[21][65][65] ;
void DP(){
    memset(dp,0,sizeof(dp));
    dp[0][20][20] = 1 ;
    for(int i=1;i<=20;i++){
        for(int j=0;j<=60;j++){
            int score1 = j-20 ;
            for(int k=0;k<=60;k++){
                int score2 = k - 20 ;
                for(int st=1;st<=9;st++){
                    int n_s1 = score1 + add_a[st] ;
                    int n_s2 = score2 + add_b[st] ;
                    dp[i][n_s1+20][n_s2+20] += dp[i-1][j][k] * p[st] ;
                }
            }
        }
    }
    printf("Round   A wins    B wins    Tie\n");
    for(int i=1;i<=20;i++){
        double a_win = 0 , b_win = 0 , tie = 0 ;

        for(int j=0;j<=60;j++){
            for(int k=0;k<=60;k++){
                if(j>k) a_win+=dp[i][j][k] ;
                else if(j<k)    b_win += dp[i][j][k] ;
                else tie += dp[i][j][k] ;
            }
        }
        printf("%5d%10.4f%%%9.4f%%%9.4f%%\n",i,a_win*100,b_win*100,tie*100);
    }
}
int main(){
        freopen("1out","w",stdout);
        DP() ;
        return 0;
}