caioj1271&&poj3071: 概率期望值2：足球

见到网上的大佬们都用了位运算。。表示看不懂就自己想了，还挺好想的（然而我不会告诉你我因为p的数组问题卡了半小时顺便D了ZZZ大佬的数据）

DP方程（伪）就是：第t轮第i个队晋级的可能=第t-1轮第i个队晋级的可能*第t-1轮第（枚举所有可以在这轮和我对战的队）队晋级的可能*战胜他的可能

所以说该怎么枚举可以在这轮和我对战的队？我们仔细研究淘汰对战表（图丑勿喷）

这里u表示在这一轮，在当前这个组里是第几个队。然后就会发现，单数组和双数组（当t=2时，3、4处于一个双数组）他要对战的队伍是不一样的，所以要分情况讨论。单数组要往下找队对战，双数组就反之。

#include<cstdio>

#include<cstring>

using namespace std;

double p[][],f[][];

int main()

{int N,n;

    while(scanf("%d",&N)!=EOF)

    {

        if(N==-)break;

        n=;for(int i=;i<=N;i++)n*=;

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

            for(int j=;j<=n;j++)

                scanf("%lf",&p[i][j]);

        memset(f,,sizeof(f));

        for(int i=;i<=n;i++)f[][i]=1.0;

        int ln=;

        for(int t=;t<=N;t++)

        {

            int u=,z=;

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

            {

                u++;if(u==ln+){u=;z=-z;}

                if(z==)

                {

                    int end=i-u+ln;

                    for(int j=end+;j<=end+ln;j++)

                        f[t][i]+=f[t-][i]*f[t-][j]*p[i][j];

                }

                else

                {

                    int str=i-u+;

                    for(int j=str-;j>=str-ln;j--)

                        f[t][i]+=f[t-][i]*f[t-][j]*p[i][j];

                }

            }

            ln*=;

        }

        int ans=;

        double mmax=;

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

            if(f[N][i]>mmax)

            {

                mmax=f[N][i];

                ans=i;

            }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

caioj1271&&poj3071: 概率期望值2：足球

最新文章

热门文章