Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator