poj 3071 可能DP-白红宇

poj 3071 可能DP

阅读量：7086 次

发布时间：2019-06-28

本文共 1126 字，大约阅读时间需要 3 分钟。

http://poj.org/problem?

id=3071

推方程不难，可是难在怎么算

dp[i][j]表示第i场时第j仅仅队伍存活下来的概率

方程：dp[i][j]=sigma(dp[i-1][j]*p[j][k]*dp[i-1][k])

j,k在同一场的条件：if(((k>>(i-1))^1)==(j>>(i-1)))即推断k的第i位前的数没有比过的是否与j的在同一棵子树上。（i从1取，j,k从0取）

题解參考 http://blog.csdn.net/pbj1203/article/details/6950450

//#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i
               
                >1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 1000;double p[MAXN][MAXN],dp[MAXN][MAXN];int N,n;int solve(){ CL(dp,0); rep(i,0,n)/ dp[0][i]=1; repe(i,1,N) rep(j,0,n) rep(k,0,n) if(((k>>(i-1))^1) == (j>>(i-1))) dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k]; int ans=-1; dp[0][0]=-1; rep(j,0,n) if(dp[N][j]>dp[0][0]) { ans=j; dp[0][0]=dp[N][j]; } return ans+1;}int main(){ while(~scanf("%d",&N) && N!=-1) { n=1<