题目链接//http://acm.hdu.edu.cn/showproblem.php?pid=4800
Problem Description
A role-playing game (RPG and sometimes roleplaying game) is a game in which players assume the roles of characters in a fictional setting. Players take responsibility for acting out these roles within a narrative, either through literal acting or through a process of structured decision-making or character development.
Recently, Josephina is busy playing a RPG named TX3. In this game, M characters are available to by selected by players. In the whole game, Josephina is most interested in the “Challenge Game” part.
The Challenge Game is a team play game. A challenger team is made up of three players, and the three characters used by players in the team are required to be different. At the beginning of the Challenge Game, the players can choose any characters combination as the start team. Then, they will fight with N AI teams one after another. There is a special rule in the Challenge Game: once the challenger team beat an AI team, they have a chance to change the current characters combination with the AI team. Anyway, the challenger team can insist on using the current team and ignore the exchange opportunity. Note that the players can only change the characters combination to the latest defeated AI team. The challenger team gets victory only if they beat all the AI teams.
Josephina is good at statistics, and she writes a table to record the winning rate between all different character combinations. She wants to know the maximum winning probability if she always chooses best strategy in the game. Can you help her?

Input
There are multiple test cases. The first line of each test case is an integer M (3 ≤ M ≤ 10), which indicates the number of characters. The following is a matrix T whose size is R × R. R equals to C(M, 3). T(i, j) indicates the winning rate of team i when it is faced with team j. We guarantee that T(i, j) + T(j, i) = 1.0. All winning rates will retain two decimal places. An integer N (1 ≤ N ≤ 10000) is given next, which indicates the number of AI teams. The following line contains N integers which are the IDs (0-based) of the AI teams. The IDs can be duplicated.

Output
For each test case, please output the maximum winning probability if Josephina uses the best strategy in the game. For each answer, an absolute error not more than 1e-6 is acceptable.

Sample Input
4
0.50 0.50 0.20 0.30
0.50 0.50 0.90 0.40
0.80 0.10 0.50 0.60
0.70 0.60 0.40 0.50
3
0 1 2

Sample Output
0.378000

大致题意：
3个字符组成一种牌，每种牌间有对应的胜负的概率，你要与n个ai机器人战斗，每与一位机器人战斗后你可以与改机器人交换牌，也可以不换。求最终获胜的最大概率，（开始时可任意选择一种牌）；

思路：
假设我们用j号牌打败了第i个机器人，那么我们下一轮手上的牌便可能是第i个ai的牌或j号牌。
于是我们定义dp[i][j]为从第i个机器人开始，用j号牌打败第i个ai并最终获胜的概率。由于我们下一步手上的牌仅有两种，假设下一轮的最大获胜概率已知的话，有转移方程：
dp[i][j] = t[j][id[i]] * max(dp[i+1][j] , dp[i+1][id[i]]);//id[i]为第i个ai的牌，t[i][j]为i牌打败j牌的概率

由转移方程我们很容易就可以从最后一个ai开始推回到第一个ai
初始条件：
dp[n-1][i]=t[i][id[n-1]];// 枚举所以牌型；
答案为最大的dp[0][i]

//HDU 4800 Josephina and RPG

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//const double pi=atan(1)*4;
int m,n;
float t[200][200];
int id[10005];
int c[11]={0,0,0,1,4,10,20,35,56,84,120};//所有的c（m，3）
float dp[10005][125];

int main(){
    while(scanf("%d",&m)!=EOF){
        for(int i=0;i<c[m];i++){
            for(int j=0;j<c[m];j++){
                scanf("%f",&t[i][j]);
            }
        }
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&id[i]);
        }
        for(int i=0;i<c[m];i++){
            dp[n-1][i]=t[i][id[n-1]];
        }
        for(int i=n-2;i>=0;i--){
            for(int j=0;j<c[m];j++){
                dp[i][j]=t[j][id[i]]*max(dp[i+1][j],dp[i+1][id[i]]);
            }
        }
        float ans=0;
        for(int i=0;i<c[m];i++){
            ans=max(ans,dp[0][i]);
        }
            printf("%.6f\n",ans);
    }
}