kao,WA了那么多次这题目数据是错的,两个人的血量弄错了,输入的 A的血量其实是B的,输入B的其实是A的,由于有平局现象的干扰,所以一开始先把平局包括进去 的 A赢的概率B赢的概率都算出来,然后减去以后就是平局的概率,再在已经除去平局的情况里 算一下A赢的概率,B赢得概率计算出来,这样就可以计算了,
假设方程dp[i][j]代表 A赢了j次B赢了i次的概率,然后状态转移就比较简单了 :
dp[i][j] += dp[i][j - 1] * a_win;
dp[i][j] += dp[i - 1][j] * b_win;
然后就是需要注意的是 B至多赢n-1次,而A必须恰好赢m次,
一开始没注意,当A已经赢了以后第二个状态转移已经不需要再加了,一开始没注意,第二个状态转移多加了一次
还有这破题目,数组要是开dp[2050][2050]就会MLE....必须差不多刚好2005 * 2005
double p1[7],p2[7]; int n,m; double a_win,b_win; double dp[2000 + 5][2000 + 5]; void init() { memset(dp,0.00,sizeof(dp)); } bool input() { while(cin>>m>>n) { for(int i=1;i<=6;i++)cin>>p1[i]; for(int i=1;i<=6;i++)cin>>p2[i]; return false; } return true; } void cal() { a_win = 0.00; for(int i=2;i<=6;i++) for(int j=1;j<i;j++) a_win += p1[i] * p2[j]; b_win = 0.00; for(int i=2;i<=6;i++) for(int j=1;j<i;j++) b_win += p2[i] * p1[j]; double aa = a_win; double bb = b_win; double p = 1.00 - aa - bb; if(p + eps == 1.00 + eps) {a_win = 0.00,b_win = 0.00;} else { a_win = aa/(1 - p); b_win = bb/(1 - p); } dp[0][0] = 1.00; for(int j=0;j<=m;j++) { for(int i=0;i<n;i++) { if(i == 0 && j == 0)continue; if(j)dp[i][j] += dp[i][j - 1] * a_win; if(i && j != m)dp[i][j] += dp[i - 1][j] * b_win; } } double ans = 0.00; for(int i=0;i<n;i++) ans += dp[i][m]; if(ans > 1 + eps)puts("1.000000"); else printf("%.6lf\n",ans); } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }