射击游戏 （C++代码）

解题思路: 

路：一开始不理解假定A和B都足够聪明，采取让自己获胜概率尽量高的策略，你的任务是计算出A获胜的概率。

其实就是说在任意一种方式下都是取得胜利的最大概率，所以要从所有可能的情况（1~6行，从左or从右）里取一个最大的

那么直接去dfs枚举即可，注意这里涉及到了一点博弈的知识。

当状态为全0的时候是必败态，在这个状态下获胜概率为0

当前状态所能到达的下一个状态的最大获胜概率是当前状态对应的这个人的最小获胜概率，所以累加起来然后用1减掉即是我们要求的当前状态的最大获胜概率（可以理解为AB两个人一轮一轮的射击，我们现在要算A这个人最大获胜概率，那么必然等于1-下一个状态（此时为B）最大获胜概率）

--------------------- 

作者：acm_cxq 

来源：CSDN 

原文：https://blog.csdn.net/acm_cxq/article/details/52282705 

注意事项:

附上找到的解析供参考

参考代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

int n;

double dp[7][7][7][7][7][7];

double dfs(int *h)///从第一列到最后一列分别有多少个积木

{

    if(dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]]!=-1) return dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]];

    dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]]=0.0;

    for(int i=1; i<=6; i++) ///往第i行开枪

    {

        double ans=0;

        int num=0;

        for(int j=0; j<6; j++) ///枚举列

            if(h[j]>=i)

                num++;

        if(!num) break;

        for(int j=1; j<=3; j++)

        {

            int hh[6];

            for(int k=0;k<6;k++) hh[k]=h[k];

            num=0;

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

            {

                if(hh[k]>=i)

                {

                    num++;

                    hh[k]--;

                }

                if(num==j) break;

            }

            ans+=1-dfs(hh);

        }

        dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]]=max(dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]],ans/3.0);

        ans=0;

        for(int j=1; j<=3; j++)

        {

            int hh[6];

            for(int k=0;k<6;k++) hh[k]=h[k];

            num=0;

            for(int k=5; k>=0; k--)

            {

                if(h[k]>=i)

                {

                    num++;

                    hh[k]--;

                }

                if(num==j) break;

            }

            ans+=1-dfs(hh);

        }

        dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]]=max(dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]],ans/3.0);

    }

    return dp[h[0]][h[1]][h[2]][h[3]][h[4]][h[5]];

}

int main()

{

    int h[6];

    while(~scanf("%d",&n)&&n)

    {

        memset(h,0,sizeof(h));

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

            scanf("%d",&h[i]);

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

            for(int j=0; j<=6; j++)

                for(int k=0; k<=6; k++)

                    for(int l=0; l<=6; l++)

                        for(int q=0; q<=6; q++)

                            for(int w=0; w<=6; w++)

                                dp[i][j][k][l][q][w]=-1;

        printf("%.6lf\n",dfs(h));

    }

    return 0;

}

部分转载：https://blog.csdn.net/acm_cxq/article/details/52282705