LUOGU P1291 [SHOI2002]百事世界杯之旅 (期望dp)

解题思路

期望$dp$。因为这个是期望步数，所以要倒着推。那么这道题就变得一脸可做了，设$f[i]$表示还有$i$张牌没有收集的期望，那么考虑再抽一张，有$(n-i)/n$的概率抽到抽过的牌，有$i/n$的概率抽到没有抽过的牌。那么转移方程就是: $f[i]=f[i]*\dfrac{(n-i)}{n}+f[i-1]*\dfrac {i}{n}+1 $。但这样是没法继续写的，因为方程两边有同一个未知数，所以移项可得 $f[i]=f[i-1]+\dfrac{n}{i}$。

输出的格式真的6，因为要输出分数，所以要记下来分母和分子，用一个结构体记录，重载一下$+$就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int MAXN = ;

typedef long long LL;

int n,cnt,num;

struct Node{

    LL a,b;

    Node(LL u=,LL v=) {a=u;b=v;}

    friend Node operator+(const Node A,const Node B){

        Node ret;ret.a=ret.b=;

        ret.a=A.a*B.b+A.b*B.a;

        ret.b=A.b*B.b;

        LL gcd=__gcd(ret.a,ret.b);

        ret.a/=gcd;ret.b/=gcd;

        return ret;

    }

}f[MAXN];

//f[i]=f[i-1]*i/n+f[i]*(n-i)/n+1

//f[i]=f[i-1]+n/i 

int main(){

    cin>>n;

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

        f[i]=f[i-]+Node(n,i);

    if(f[n].b==) printf("%lld",f[n].a);

    else{

        LL now=f[n].a/f[n].b;

        LL fuck=now;

        while(fuck) {cnt++;fuck/=;}

        for(int i=;i<=cnt;i++) putchar(' ');

        printf("%lld\n",f[n].a-now*f[n].b);

        if(now) printf("%lld",now);

        LL shit=f[n].b;

        while(shit) {num++;shit/=;}

        for(int i=;i<=num;i++) putchar('-');putchar('\n');

//        printf("-\n");

        for(int i=;i<=cnt;i++) putchar(' ');

        printf("%lld\n",f[n].b);

    }

    return ;

}

巴特西

LUOGU P1291 [SHOI2002]百事世界杯之旅 (期望dp)

最新文章

热门文章