2015
09-18

# HDU 4800-Josephina and RPG-动态规划-[解题报告]HOJ

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

PS:

dp[i][j]：战胜第i支队伍时，当前的队伍为j！

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 147;
double dp[10017][maxn], p[maxn][maxn];
//dp[i][j]：战胜第i支队伍时，当前的队伍为j！
int a[10017];
int n, m;

void solve()
{
for(int i = 0; i <= m; i++)
{
dp[0][i] = 1;//初始值
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
dp[i+1][j] = max(dp[i+1][j], dp[i][j]*p[j][a[i+1]]);//不换
dp[i+1][a[i+1]] = max(dp[i+1][a[i+1]], dp[i][j]*p[j][a[i+1]]);//换
}
}
}
int main()
{
while(~scanf("%d",&m))
{
memset(dp,0,sizeof(dp));
m = m*(m-1)*(m-2)/6;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%lf",&p[i][j]);
}
}
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
}
solve();
double ans = 0;
for(int i = 0; i < m; i++)
{
ans = max(ans,dp[n][i]);
}
printf("%.6lf\n",ans);
}
return 0;
}


1. 人多，劳动力就多，就可以生产更多的产品，同时，内需也是巨大的，可以产生巨大的经济能量，所以虽然我们人均与美国差很多，但是总量上我们快追上他了，原因之一就是因为人多。这样的话，我们就可以换取在国际上更大的影响力，现实也确实是这样的。同时，人多，出现精英的数

2. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

3. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

4. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

5. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

6. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

7. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

8. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

9. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系

10. 这事肯定跟医院脱不开干系！你想想看啊，如果医院宣布治不了的人，必死的人到他那就能治，影响医院的收益是小事，关键是如果官方和医院都认定的必死的病症被证明是可以医治，并且是可以治好的，那么医院将不能堂而皇之的治死病人，那么多的持证庸医将如何谋生?整个医疗体系