Topcoder SRM579 1000pts

石头剪刀布QAQ

一看是个很油的概率dp

首先一看你很快能得出状态的表示F[i][r][p][s]

然后只要考虑r,p,s出现的次数来进行概率dp就好了

具体实现的时候细节很多（少）

如果预处理一下组合数常数短了一截。但是自信的我认为50^4根本不慌。最后还是过了。

#include<map>

#include<stack>

#include<queue>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<complex>

#include<iostream>

#include<assert.h>

#include<algorithm>

using namespace std;

#define inf 1001001001

#define infll 1001001001001001001LL

#define ll long long

#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl

#define gmax(a,b) (a)=max((a),(b))

#define gmin(a,b) (a)=min((a),(b))

#define Ri register int

#define gc getchar()

#define il inline

il int read(){

    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;}return f?x:-x;

}

#define gi read()

#define ig read()

#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);

int n;double ans,R[55],P[55],S[55];

double dp[55][55][55][55];

int main(){

    FO(rps);

    n=gi;

    for(int i=0;i<n;i++){

        R[i]=gi;R[i]/=300;

        P[i]=gi;P[i]/=300;

        S[i]=gi;S[i]/=300;

    }

    for(int a=0;a<n;a++){

        dp[a][0][0][0]=1.0;

        for(int i=0;i<n;i++)

            for(int j=i;j+1;j--)

                for(int k=i-j;k+1;k--)

                    for(int s=i-j-k;s+1;s--) {

                        if(i!=a){

                        dp[a][j+1][k][s]=dp[a][j+1][k][s]+1.0*(j+k+s+1)/(i+1)*R[i]*dp[a][j][k][s];

                        dp[a][j][k+1][s]=dp[a][j][k+1][s]+1.0*(j+k+s+1)/(i+1)*P[i]*dp[a][j][k][s];

                        dp[a][j][k][s+1]=dp[a][j][k][s+1]+1.0*(j+k+s+1)/(i+1)*S[i]*dp[a][j][k][s];

                        }dp[a][j][k][s]=dp[a][j][k][s]*(1-1.0*(j+k+s)/(i+1));

                    }

    }

    for(int i=0;i<n;i++){

        for(int j=0;j<n-i;j++){

            for(int k=0;k<n-i-j;k++){

                double r,p,s;

                r=p=s=0;

                //face i rock k scissor j paper

                for(int a=0;a<n;a++){

                    double t=dp[a][i][j][k],m=n-i-j-k;

                    r=r+dp[a][i][j][k]/m*R[a];

                    p=p+dp[a][i][j][k]/m*P[a];

                    s=s+dp[a][i][j][k]/m*S[a];

                }

                double tmp=0.0;

                gmax(tmp,3*r+p);

                gmax(tmp,3*p+s);

                gmax(tmp,3*s+r);

                /*

                old version fucking possiblities

                gmax(ans,3*r+p);

                gmax(ans,3*p+s);

                gmax(ans,3*s+r);*/

                ans+=tmp;

            }

        }

    }

    printf("%.9lf",ans);

    return 0;

}