首页 > 代码库 > UVA 10471 Gift Exchanging

UVA 10471 Gift Exchanging

2024-07-22 19:50:30   221人阅读

题意：就5种盒子，给出每个盒子个数，盒子总数，每个人选择这个盒子的概率。求这个人选择哪个盒子取得第一个朋友的概率最大，最大多少

dp[N][sta]表示当前第N个人面临状态sta（选择盒子的状态可以用13进制数表示)时的概率，

那么转移就是dp[N][sta]=sum(dp[N-1][sta-1]*G[n][k]) (表示第N个人选择第k个盒子)

那么答案应该是max(P(第1个人选择i号盒子)/总状态概率)(i<=5)

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 350000#define MAXD 15#define MAXB 10double p[MAXD][MAXB],dp[MAXD][MAXN];bool vis[MAXD][MAXN];int N,res[MAXB],gift[MAXB];double calcu(int cur,int st){    if (vis[cur][st]) return dp[cur][st];    vis[cur][st]=true;    double ans=0;    int sta=st;    for (int i=5;i>0;i--)  {res[i]=sta%13;sta/=13;}    for (int i=1;i<=5;i++)      if (res[i])    {        res[i]--;        sta=0;        for (int j=1;j<=5;j++) sta=sta*13+res[j];        ans+=calcu(cur+1,sta)*p[cur][i];        res[i]++;    }    return dp[cur][st]=ans;}int main(){    //freopen("sample.txt","r",stdin);    int T;    scanf("%d",&T);    while (T--)    {        scanf("%d",&N);        int sta=0;        for (int i=1;i<=5;i++) { scanf("%d",&gift[i]);sta=sta*13+gift[i];}        for (int i=1;i<=N;i++) for (int j=1;j<=5;j++) scanf("%lf",&p[i][j]);        memset(vis,false,sizeof(vis));        vis[N+1][0]=true;dp[N+1][0]=1;        double tmp=calcu(1,sta);        double ans=-1.0,sym;int ide;        for (int i=1;i<=5;i++)            if (gift[i])        {            gift[i]--;            sta=0;            for (int j=1;j<=5;j++) sta=sta*13+gift[j];            gift[i]++;            sym=dp[2][sta]*p[1][i]/gift[i];            if (sym/tmp>ans)            {                ans=sym/tmp;                ide=i;            }        }        printf("%d %.3lf\n",ide,ans);    }    return 0;}

 

UVA 10471 Gift Exchanging


联系
我们