POJ 1217 FOUR QUARTERS

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<set>
 6 #include<vector>
 7 #include<map>
 8 #include<algorithm>
 9 #include<cmath>
10 #include<stdlib.h>
11 using namespace std;
12 double way[9]= {0.0625,0.125,0.0625,0.125,0.25,0.125,0.0625,0.125,0.0625};
13 int a[9]= {1,1,2,0,0,1,-1,0,0};
14 int b[9]= {0,-1,-1,1,0,0,2,0,-1};
15 double dp[22][66][66];
16 void solve()
17 {
18     memset(dp,0,sizeof(dp));
19     dp[0][20][20]=1;      //dp[i][j][k],表示第i个回合，A得j分，B得k分的概率，j或k最小为-20，所以+20
20     for(int i=1; i<=20; i++)
21         for(int j=60; j>=0; j--){
22             int score1=j-20;
23             for(int k=60; k>=0; k--){
24                 int score2=k-20;
25                 if(dp[i-1][j][k]>0){
26                     for(int s=0; s<9; s++)
27                         dp[i][score1+20+a[s]][score2+20+b[s] ]+=dp[i-1][j][k]*way[s];
28                 }
29 
30             }
31         }
32     printf("Round   A wins    B wins    Tie\n");
33     for(int i=1; i<=20; i++)
34     {
35         double a_win = 0 , b_win = 0 , tie = 0 ;
36         for(int j=0; j<=60; j++){
37             for(int k=0; k<=60; k++){
38                 if(j>k) a_win+=dp[i][j][k] ;
39                 else if(j<k)    b_win += dp[i][j][k] ;
40                 else tie += dp[i][j][k] ;
41             }
42         }
43         printf("%5d%10.4f%%%9.4f%%%9.4f%%\n",i,a_win*100,b_win*100,tie*100);
44     }
45 }
46 int main()
47 {
48     solve();
49 }