Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:能提示提示怎样用DP来做吗？？？多谢指教！！！

Posted by lzqxh at 2011-09-15 00:16:05 on Problem 3071
In Reply To:能提示提示怎样用DP来做吗？？？多谢指教！！！ Posted by:zhangyin at 2007-09-02 09:23:20

dp[i][j]表示第i轮比赛j存活的概率
dp[i][j] = dp[i-1][j] * ( dp[i-1][t1]*data[j][t1] + dp[i-1][t1+1]*data[j][t1+1]...dp[i-1][t1+(1<<(i-1))-1]*data[i][t1+(1<<(i-1))-1] );
很容易知道第i轮比赛,j需要跟1<<(i-1) 个人比赛。算出t1然后就得到上面方程。。。。j想在第i轮存活，必须i-1轮存活，再乘以第i轮打败对手，枚举出对手就可以算出

Followed by:

Post your reply here:

Home Page Go Back To top