1 条题解

  • 0
    @ 2026-4-27 9:47:28
    
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    double a[16][11];
    double b[6][6];
    double win[6][6][6];
    double f[3][7][7][7];
    double ans=0,tot=0;
    bool use[16];
    void dfs(int p)
    {
        if(p>5)
        {
            f[0][1][1][1]=f[1][1][1][1]=f[2][1][1][1]=1.0/3.0;
            for(int i=1;i<=6;i++)
                for(int j=1;j<=6;j++)
                    for(int k=1;k<=6;k++)
                    {
                        if(i>1)
                        {
                            f[0][i][j][k]=f[1][i-1][j][k]*win[4][k][i-1]+f[2][i-1][j][k]*win[2][j][i-1];
                            if(i==6)
                                f[0][i][j][k]+=f[0][i][j-1][k]*win[5][k][j-1]+f[0][i][j][k-1]*win[3][j][k-1];               
                        }
                        if(j>1)
                        {
                            f[1][i][j][k]=f[0][i][j-1][k]*win[5][k][j-1]+f[2][i][j-1][k]*win[0][i][j-1];
                            if(j==6)
                                f[1][i][j][k]+=f[1][i-1][j][k]*win[4][k][i-1]+f[1][i][j][k-1]*win[1][i][k-1];      
                        }
                        if(k>1)
                        {
                            f[2][i][j][k]=f[0][i][j][k-1]*win[3][j][k-1]+f[1][i][j][k-1]*win[1][i][k-1];
                            if(k==6)
                                f[2][i][j][k]+=f[2][i-1][j][k]*win[2][j][i-1]+f[2][i][j-1][k]*win[0][i][j-1];                
                        }
            }
            tot=0;
            for(int i=1;i<=5;i++)
                tot+=f[1][i][6][6];
            ans=max(ans,tot);
            return;
        }
        for(int l=1;l<=n;l++)
        {
            if(!use[l])
            {
                use[l]=1;
                for(int r=1;r<=5;r++)
                    win[0][p][r]=a[l][r],win[2][r][p]=1.0-a[l][r];
                for(int r=1;r<=5;r++)
                    win[1][p][r]=a[l][r+5],win[4][r][p]=1.0-a[l][r+5];
                dfs(p+1);
                use[l]=0;
            }   
        } 
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=10;j++)
                scanf("%lf",&a[i][j]);  
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
            {
                scanf("%lf",&b[i][j]);
                win[3][i][j]=b[i][j];
                win[5][j][i]=1.0-b[i][j];
            }
        dfs(1);
        printf("%.6lf",ans);
    }
    
    • 1

    「SHOI 早期试题选」三国围棋对抗赛

    信息

    ID
    10497
    时间
    1000ms
    内存
    8MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者