牛客小白月赛13 小A买彩票 （记忆化搜索）

时间：2024-05-23 18:36:02

链接：https://ac.nowcoder.com/acm/contest/549/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。

输入描述:

一行一个整数N，为小A购买的彩票数量一行一个整数N，为小A购买的彩票数量

输出描述:

输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。输出一个最简分数a/b，表示小A不亏本的概率。若概率为1，则输出1/1，概率为0，则输出0/1。
示例1

输入

复制

2

输出

复制

3/8

备注:

0≤n≤300≤n≤30

解题思路：设dp[i][j]表示摸j次和中奖i元的情况数，然后只要枚举中奖3n-4n 元的所有情况数，总情况数是4^n，比一下就可以了。
代码：
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<cmath>

#include<list>

#include<deque>

#include<cstdlib>

#include<bitset>

#include<stack>

#include<map>

#include<cstdio>

#include<queue>

using namespace std;

typedef long long ll;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const ll mod=1e9+;

const int maxn=;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const int dir[][]={{,},{-,},{,},{,-}};

const int MAXN=2e6+;

ll n,m,ans;

ll dp[][];

ll dfs(int x,int cnt){

    //cout<<x<<" "<<cnt<<endl;

    if(cnt==n+){

        if(x==) return ;

        else return ;

    }

    if(dp[x][cnt]!=-)return dp[x][cnt];

    ll ans=;

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

        if(x>=i)ans+=dfs(x-i,cnt+);

    }

    //cout<<x<<" "<<cnt<<" "<<ans<<endl;

    return dp[x][cnt]=ans;

}

int main(){

    scanf("%lld",&n);

    ll x=;

    if(n==){

        puts("1/1");

        return ;

    }

    memset(dp,-,sizeof(dp));

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

        x+=dfs(i,);

    }

    ll y=;

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

        y*=;

    }

    ll z=gcd(x,y);

    cout<<x/z<<"/"<<y/z<<endl;

    return ;

}

相关文章