首页 > 代码库 > POJ 1217 FOUR QUARTERS

POJ 1217 FOUR QUARTERS

题目意思是,AB两个人掷硬币,每次一个人掷两次,然后对应图标里面得分,要你输出前20回合 A赢,B赢,或是平均的概率

dp还是不怎么会,参考别人代码才敲出来的

 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,所以+2020     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 }