题意:有(1<
en….网上当然也后不少解题报告，但是很多直接给出状态转移方程和贴出代码，而少了其中重要的推断过程，我觉得不是很好。所以自己给写一个较为详细的过程
首先呢，以n==3为例子，即8支队伍参赛。一种比赛情形是这样的
由图可知，在题中给定n后，需要比赛n轮即可知道冠军队伍是谁，我这里多了个第0轮是为了后面计算需要
其次，对于DP的题目，我们 首先要明确状态转移方程代表的含义是什么，我们 已知什么，未知什么，怎么去确定合适的方程，这些是很重要的，当然，推出转移方程到后面更难的题目则是更重要的。
既然要求出最终能获胜的队伍，即 求出每个队伍的在最后一轮的胜率，最后取一个最大值就ok了。并且，获得 冠军的那支队伍既然能够到达最后一轮，那么，它一定经历了所有轮次的比赛，并且都赢了。在这每一轮比赛的胜率，就是子问题了。这是很简单就可以得出的。所以， 后一轮的胜率，肯定是由上一轮的胜率决定的。
所以， DP[i][j]可以这么定义，它表示为在第i轮中，第j只队伍的胜率。这也符合求解问题的逻辑，我们已知总共的 轮数(n)，已知所有 队伍的数量(1<
DP的含义确定了，那么，状态转移方程怎么来呢？？
首先，dp数组的 第一维表示的是整个赛事的轮数，所以外面有一层循环，接着 ，第二维表示每只队伍，所以又一层循环遍历每一只队伍。那么对应的概率到底怎么来呢…..
因为对于树中的 每个结点代表对应DP[i][j]的概率，即两支队伍某一方击败另一方，并且，这两支队伍在上一轮中都双双各自获胜，我们 直接看最后一轮比赛/最上面一个结点，因为，所有底下结点是子问题，性质都一样，所以可以得到部分转移方程:(假设最后一轮是j赢了，此时i==3,概率为DP[i][j])
DP[i][j] = DP[i-1][j] * DP[i-1][k] * ???;
DP[I-1][j]：表示本轮的赢家j在上一轮获胜的概率，上一轮一定是获胜了的再能到这一轮
DP[i-1][k]：表示本轮赢家j遇见的对手k，k在上一轮获胜的概率，k也晋级到了这一轮
???：这个表示什么呢???因为此时DP[i][j]表示这一轮是j获胜的概率，所以j战胜了k，那么胜率是多少呢??
在题中输入的矩阵中 第j行k列就是这里的概率
所以完整的状态转移方程：(当前概率+=上一轮二者分别获胜的概率 * 这一轮一方胜另一方的概率)
别以为到这里就结束了，k 的范围还没确定呢！！
从图中可知，在第二轮中 3号结点不会遇见所有的对手， 只有可能遇见来自另一边的5,6,7,8的某一个，
而1,2,4是不可能再遇见了(已经淘汰了)。那么，k的编号怎么判断呢？？(关键）
假设最后是 j和k进行决赛，那么表明j和k一定是在最后一轮相遇了，在倒数第二轮它们不会相遇，因为它们各自再进行半决赛（好像说了句废话，但是….）k的范围就这样确定。
因为到了最后一轮，所以遍历轮数的编号i此时为3,如图中，j为3，最后是k==7与之对决。
它们满足这样了个关系：
3 /(1<
公式是这样的
即对于某个j，判断k是否能和j同时成为一个点的左右孩子结点。这个条件就满足了对可能遇见的对手的的选取
这里还是要稍微思考下的。
Original: https://www.cnblogs.com/ygsworld/p/11312218.html
Author: 回忆酿的甜
Title: POJ3071(Football)–概率DP
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582138/
转载文章受原作者版权保护。转载请注明原作者出处！