2013 Asia Changsha Regional Contest---Josephi…

2018-06-17 23:43:31来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

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
 
Source
2013 Asia Changsha Regional Contest
 
 
Recommend
We have carefully selected several similar problems for you:  5901 5899 5898 5897 5896 
 
 
题意:输入M,表示有K=C(M,3) 种机器人,然后输入k*k的矩阵 s[i][j]表示第i种机器人打赢第j种机器人的概率,接下来输入N和N个数,每个数表示N个机器人的种类,现在你可以任选一种机器人依次和这N个机器人打,每次打赢一个机器人后,你可以和他交换机器人,求打败N个机器人的最大概率;
 
思路:定义dp[i] 表示交换或没交换 当前你的机器人为i 时打败前x个机器人的最大概率;
 
代码如下:
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
typedef long long LL;
double s[1005][1005];
double d1[1005];
int a[10005];

int main()
{
    int M,N;
    while(scanf("%d",&M)!=EOF)
    {
        M=M*(M-1)*(M-2)/6;
        for(int i=0;i<M;i++)
        {
            for(int j=0;j<M;j++)
                scanf("%lf",&s[i][j]);
        }
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<M;i++)
            d1[i]=1.0;
        for(int i=0;i<N;i++)
        {
            int x=a[i];
            double r=0.0;
            for(int j=0;j<M;j++)
            {
                d1[j]=d1[j]*s[j][x];
                r=max(r,d1[j]);
            }
            d1[x]=max(d1[x],r);
        }
        printf("%.6lf\n",d1[a[N-1]]);
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 1061 青蛙的约会 扩展欧几里得

下一篇:函数声明和函数定义中的默认参数浅析