首页 > 代码库 > hdu 4800 Josephina and RPG (动态规划)
hdu 4800 Josephina and RPG (动态规划)
Josephina and RPG
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 923 Accepted Submission(s): 261
Special Judge
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?
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
题意:m个角色组成C(M, 3)支队伍,N个对手,刚开始可以任选一支队伍作为棋子,打败一支队伍后可以选择打败的这支队伍作为棋子,继续作战,求打败所有队伍的最大概率。。
思路:从最后一次比赛算,当前队伍i打败第m个对手c[j]的概率为dp[i][c[m]]=p[i][c[m]];
对于倒数第二次比赛,某一支队伍打败第m-1个对手的最大概率为:
dp[i][c[m-1]]=max(dp[i][c[m-1]],dp[c[m-1][c[m]])*p[i][c[m-1]],
即当前队伍比这一场,下一场可以换队伍,选择两个中较大的一个。
#include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<vector> using namespace std; #define LL __int64 #define N 10010 #define M 150 const int inf=0x1f1f1f1f; double p[M][M]; double dp[N][M]; int c[N]; void solve(int r,int m) { int i,j,k; for(k=m-2;k>=0;k--) { j=c[k]; int t=c[k+1]; for(i=0;i<r;i++) { dp[i][j]=max(dp[i][t],dp[j][t])*p[i][j]; } } double ans=0; for(i=0;i<r;i++) ans=max(ans,dp[i][c[0]]); printf("%.6f\n",ans); } int main() { int n,r,i,j,m; while(~scanf("%d",&n)) { r=n*(n-1)*(n-2)/6; for(i=0;i<r;i++) { for(j=0;j<r;j++) { scanf("%lf",&p[i][j]); } } scanf("%d",&m); for(i=0;i<m;i++) scanf("%d",&c[i]); memset(dp,0,sizeof(dp)); for(i=0;i<r;i++) dp[i][c[m-1]]=p[i][c[m-1]]; solve(r,m); } return 0; }
hdu 4800 Josephina and RPG (动态规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。