HDU - 1099 - Lottery

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

最最简单的概率dp，完全是等概率转移。

设dp[i]为已有i张票，还需要抽几次才能集齐的期望。

那么dp[n]=0，因为我们已经集齐了。

\[dp[i]=(\frac{i}{n}*dp[i]+\frac{n-i}{n}*dp[i+1])+1
\]

移项得答案。

然后写个分数类，注意约分。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fraction{

    ll fz;

    ll fm;

    Fraction(){}

    Fraction(ll z,ll m):fz(z),fm(m){}

    Fraction operator+(Fraction f){

        ll m=fm/__gcd(fm,f.fm)*f.fm;

        Fraction res;

        res.fz=fz*(m/fm)+f.fz*(m/f.fm);

        res.fm=m;

        res.tf();

        return res;

    }

    Fraction operator-(Fraction f){

        ll m=fm/__gcd(fm,f.fm)*f.fm;

        Fraction res;

        res.fz=fz*(m/fm)-f.fz*(m/f.fm);

        res.fm=m;

        res.tf();

        return res;

    }

    Fraction operator*(Fraction f){

        Fraction res;

        res.fz=fz*f.fz;

        res.fm=fm*f.fm;

        res.tf();

        return res;

    }

    void tf(){

        ll g=__gcd(fz,fm);

        fz/=g;

        fm/=g;

    }

    void show(){

        ll zs=fz/fm;

        ll ys=fz%fm;

        if(ys==0){

            cout<<zs<<endl;

        }

        else{

            string l1,l2,l3;

            l1=" ";

            l2=" ";

            l3=" ";

            while(zs){

                l2=char(zs%10+'0')+l2;

                zs/=10;

                l1+=" ";

                l3+=" ";

            }

            ll cfm=fm;

            string n3="";

            string n2="";

            while(cfm){

                n3=char(cfm%10+'0')+n3;

                cfm/=10;

                n2+="-";

            }

            l3+=n3;

            l2+=n2;

            string n1="";

            ll cfz=ys;

            while(cfz){

                n1=char(cfz%10+'0')+n1;

                cfz/=10;

            }

            l1+=n1;

            cout<<l1<<endl<<l2<<endl<<l3<<endl;

        }

    }

};

Fraction dp[23];

int main(){

    int n;

    while(cin>>n){

        dp[n]=Fraction(0,1);

        for(int i=n-1;i>=0;i--){

            dp[i]=dp[i+1]+Fraction(n,n-i);

        }

        dp[0].show();

    }

}

巴特西

HDU - 1099 - Lottery - 概率dp

最新文章

热门文章