题目描述
小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≤30
题意很简单就是：花3元买彩票，彩票可能是1,2,3,4;问买n张彩票不亏本的概率多大（最简分数）
题解：知识点：DP枚举
首先我们要得到的是不亏本的概率：
所以我们把问题转化成不亏本的数量和总数量。
总数量好说就是类似2进制枚举的总可能性。也就是 。
不亏本的数量：首先不亏本的范围是3 * n~4 * n，就是用二维DP(i,j)来表示，i表示第几个 j表示多少钱 。所以i是（1 ~ n），到达每个i时可能会有（i ~ 4* i）这么多钱，所以j的范围是(i ~ 4* i);
状态转移方程：dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4];
dp(i,j)状态可以从上一个(dp(i-1,x))转移过来也就是，上一个可以买到（1/2/3/4）变成dp（i，j）.
最后扫一遍（3n~4n）总数量就是不亏本的数量。
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[50][10100];
string str,s;
ll qpow(ll a,ll b){
ll sum=1;
while(b){
if(b&1) sum=sum*a;
b>>=1;
a=a*a;
}
return sum;
}
ll gcd(ll a,ll b){
while(b){
ll t=a%b;
a=b;
b=t;
}
return a;
}
int main(){
n=read();
dp[0][0]=1;
//dp(i,j) i表示第几个 j表示多少钱
for(int i=1;i<=n;i++)
for(int j=i;j<=i*4;j++)
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4];//这个状态可以从这次四个继承过来
sum=qpow(4,n); //总的可能性 就是4^n
for(int i=3*n;i<=n*4;i++)
ans+=dp[n][i];//不亏本的可能性；
ll g=gcd(ans,sum);
printf("%lld/%lld\n",ans/g,sum/g);
return 0;
}
京公网安备 11010502036488号