首页 > 代码库 > uva10417 概率DP

uva10417 概率DP

2024-08-06 13:13:28   215人阅读

这题 to[i][j] 为第i个人送j这个礼物的概率 我们用13进制进行压缩这个留下的的礼物的个数，这样我们将dp[i][k]表示为当第i个人放完礼物后得到的状态为k时的概率，那么通过记忆化搜索我们就得到了我们想要的状态概率即 dp[i][k]+={dp[i+1][k-aj]*to[i][aj]}，好那么现在如果我去拿第一个礼物我正确的概率，我们 可以先知道好朋友放第一个的概率为

假设S为最初礼物的状态

pop=dp[1][S-a1]*to[0][1]/dp[0][S],这个是好朋友送了第一个礼物的概率，那么现在对于第一种礼物他有digit【0】个我们需要有1/digit[0]的概率去得到这个礼物，以此类推去得到第1个第2个等等。。。

#include <iostream>#include <cstdio>#include <algorithm>#include <string.h>using namespace std;const int maxn=5;const int MAXM=13*13*13*13*13+5;int gift[maxn],n;double dp[13][MAXM],to[13][maxn];bool vis[13][MAXM];int A[maxn];double dfs(int loc, int G){    if(vis[loc][G]) return dp[loc][G];    int K=G;    for(int i=4; i>=0; --i)    {         A[i] = K%13 ; K /= 13 ;    }    double ans=0;    for(int i=0; i<5; ++i)    if( A[i] ){           A[ i ]--;           K = 0;           for( int j = 0 ; j<5 ; ++ j )             K = K * 13 + A[ j ] ;          ans+=dfs( loc + 1 , K ) * to[ loc ][ i ] ;          A[i]++;    }    vis[loc][G]=true;    return dp[loc][G]=ans;}int main(){   int cas;   scanf("%d",&cas);   while( cas -- ){       scanf("%d",&n);       for(int i=0; i<5; ++i)        scanf("%d",&gift[i]);       for(int i=0; i<n; ++i)        for(int j=0; j<5; ++ j)           scanf("%lf",&to[i][j]);       memset(dp,0,sizeof(dp));       memset(vis,false,sizeof(vis));      vis[n][0]=1;      dp[n][0]=1;      int k=0;      for(int i=0;i<5; ++i ){           k=k*13+gift[i];      }      double res=dfs(0,k);      int  ans=1;      double pans=-1;      for(int i=0; i<5; ++i)if(gift[i]){          gift[i]--;          k=0;          for(int j=0; j<5; ++j)            k=k*13+gift[j];            gift[i]++;          double a=dp[1][k]*to[0][i]/gift[i]/res;          if(a>pans){             ans=i+1; pans=a;          }      }      printf("%d %.3lf\n",ans,pans);   }    return 0;}
View Code

 

uva10417 概率DP


联系
我们