Aizu 2303 Marathon Match （概率）

因为第i个人休息j次服从二项分布，算一下组合数。

数据范围小。

求出第i个人休息j次的概率和对应的时间之后，全概率公式暴力统计。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 101,maxm = 51;
int P[maxn],T[maxn],V[maxn];
long long C[maxm][maxm];
double rst[maxn][maxm];
double tim[maxn][maxm];
//const double eps = 1e-11;
//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int n,m,l; scanf("%d%d%d",&n,&m,&l);
    C[0][0] = 1;
    for(int i = 1; i < maxm; i++){
        C[i][i] = C[i][0] = 1;
        for(int j = 1; j < i; j++){
            C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
        //cout<<C[i][i/2]<<endl;
    }
    for(int i = 0; i < n; i++){
        scanf("%d%d%d",P+i,T+i,V+i);
    }
    int rt = 0;
    for(int i = 0; i < n; i++){
        double p = P[i]/100., t0 = l*1./V[i];
        for(int j = 0; j <= m; j++){
            rst[i][j] = C[m][j]*(pow(p,j))*(pow(1-p,m-j));
            tim[i][j] = t0+j*T[i];
        }
        //for(int j = 1; j <= m; j++){
       //     rst[i][j] += rst[i][j-1];
      //  }
    }
    for(int i = 0; i < n; i++){
        double ans = 0;
        for(int j = 0; j <= m; j++){
            double t = tim[i][j], wn = 1;
            for(int k = 0; k < n; k++){
                if(k == i) continue;
                double twn = 0;
                for(int j2 = m; j2 >= 0; j2--){
                    if(tim[k][j2] <= t) break;
                    twn += rst[k][j2];
                }
                wn *= twn;
            }
            ans += wn*rst[i][j];
        }
        printf("%lf
",ans);
    }
    return 0;
}