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

链接: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 ;
}
上一篇:c语言知识点总结(摘自head first c)


下一篇:上线啦,PP.io!