hdu-5985 概率DP

http://acm.hdu.edu.cn/showproblem.php?pid=5985

作为队里负责动态规划的同学，做不出来好无奈啊。思考了一个下午，最好还是参考了别人的思想才写出来，数学啊！！！

这题随着K的增长，贡献的数值越来越少，所以只要K足够大（100左右就够了，一开始写30WA了），之后的就可以不考虑了。

那么对于每个K，我们又可以枚举每种硬币是最后留下来的那种，那么其他硬币必须是被耗尽的。但是还有一个隐藏要求，就是在第K次之前的一次时，其他硬币不能全部耗尽，不然就不存在第K次了！

这里千万不要用P(其余硬币在K-1次没有耗尽)*P(其余硬币在K次耗尽了)，这两个并不是独立事件！

因为K=1是不存在违反隐藏要求的情况的，之前必然有硬币。而K>=2时如果直接用P(i类硬币未用尽)*P(其余硬币用尽)则会包含之前就已经剩最后一种，然后再删掉一部分得到第K次依旧剩最后一种的情况。

所以在计算的时候，把之后还有硬币被消除的那一部分概率给删去，剩下的就能保证当前是最后一次了。（此部分存疑，个人认为即时这样做了，还是不对的，奈何这样写就AC，我改了就WA）

#include<iostream>

#include <cstring>

#include <string>

#include <cstdio>

#define LL long long

using namespace std;

const LL K=;

double dp[][K][];//0: at least 1:dead all

int s[];

double p[];

double fastMi(double a,int b)

{

    double mut=;

    while(b)

    {

        if(b%!=)

            mut*=a;

        a*=a;

        b/=;

    }

    return mut;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

        for(int i=; i<n; i++)

            scanf("%d %lf",&s[i],&p[i]);

        for(int i=; i<n; i++)

        {

            for(int k=; k<K; k++)

            {

                dp[i][k][]=fastMi(-fastMi(p[i],k),s[i]);

                dp[i][k][]=-dp[i][k][];

            }

        }

        if(n==)

        {

            puts("1.000000");

            continue;

        }

        for(int i=; i<n; i++)

        {

            double ans=0.0;

            for(int k=; k<K-; k++)

            {

                double px=dp[i][k][]-dp[i][k+][];

                for(int j=; j<n; j++)

                {

                    if(j==i)continue;

                    px*=dp[j][k][];

                }

                ans+=px;

            }

            if(i==n-)

                printf("%.6f\n",ans);

            else printf("%.6f ",ans);

        }

    }

     return ;

}

巴特西

hdu-5985 概率DP

最新文章

热门文章