A笔试题（4.2）概率dp

题目描述

原始a=b=n，n为输入。数据范围1e9。
四种等概率操作：
1.(a-100, b)
2.(a-75, b-25)
3.(a-50, b-50)
4.(a-25, b-75)
直到a<=0或b<=0时停止。

记a先到0的概率为p(a)，b先到0的概率为p(b)，ab同时到0的概率为p(ab)
求：对于输入的n，输出p(a)+0.5*p(ab)

---

化简

(n+24)/25

概率dp

dp[i,j]=dp[i-4,j]+dp[i-3,j-1]+dp[i-2,j-2]+dp[i-1,j-3];

打表

数据范围超过几百的时候，dp[i,i]已经是1.00000000了，直接判断。

代码（赛后写的，不保证对）

---

# include<cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <utility>
# include <map>
# define mp make_pair
# define pff pair<float, float>
# define pfff pair<float, pair<float, float> >
using namespace std;
pfff dp[1005][1005];
int main()
{
    int T;
    scanf("%d", &T);
    memset(dp, 0, sizeof(dp));
    dp[0][0] = mp(0.0, mp(1.0, 0.0));
    for(int i = 1; i < 1000; i++){dp[i][0] = mp(0.0, mp(0.0, 1.0));dp[0][i] = mp(1.0, mp(0.0, 0.0));}
    for(int i = 1; i < 1000; i++){
        for(int j = 1; j < 1000; j++){
            int pointeri = i, pointerj = j;
            int pos[5][5] = {{-4,0}, {-3,-1}, {-2,-2}, {-1,-3}};
            for(int k = 0; k < 4; k++){
                pointeri = max(0, i+pos[k][0]);
                pointerj = max(0, j+pos[k][1]);
                //printf("%d-%d ", pointeri, pointerj);
                dp[i][j].first += 0.25*dp[pointeri][pointerj].first;
                dp[i][j].second.first += 0.25*dp[pointeri][pointerj].second.first;
                dp[i][j].second.second += 0.25*dp[pointeri][pointerj].second.second;
            }//printf("\n");
        }
    }
    while(T--)
    {
        int n;
        scanf("%d", &n);
        n = (n+24)/25;
        if(n > 500)printf("1.00000000\n");
        else{
            pfff ans = dp[n][n];
            printf("%.8f\n",(ans.first + ans.second.first*0.5));
        }
        //mm.clear();
    }
    //for(int i = 0; i < 1000; i++){
      //      pfff ans = dp[i][i];
        //    printf("%d--%.8f\n", i, (ans.first + ans.second.first*0.5));
    //}
    return 0;
}