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

题目描述

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

输入描述: 

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

输出描述: 

		

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

题型：

动态规划--求方案数的变式--求有效的方案数在总方案数中的占比

思路：

这道题本质上还是求方案数，相当于是求有效的方案数在总方案数的占比
先看总方案数量，很简单：4^n;
再看有效的方案数量：考虑动态规划
1.明确原问题：购买n张彩票，求不亏本的概率
2.明确子问题：购买i张彩票，不亏本的概率为j，但由于j是一个分数，所以我们转化一下思路-->购买i张彩票，获得的钱数为j
3.明确状态转移方程：dp[i][j]为购买i张彩票，获得的钱数为j的方案数，即dp[i][j]=dp[i][j]+dp[i-1][j-1](j>=1时加上)+dp[i-1][j-2](j>=2时加上)+dp[i-1][j-3](j>=3时加上)+dp[i-1][j-4](j>=4时加上);
4.明确有效方案总数的计算：因为不亏本-->至少要获得3*n的钱数，所以dp[n][i]从i=3*n开始，一直累加到4*n为止（因为一张彩票最多出4钱，所以最多获得的钱数为4*n），获得的累加值就是有效的方案数
5.最后不要忘记方案数约分，最简比用__gcd()函数实现(a/b==(a/gcd(a,b))/(b/(gcd(a,b))))

代码：

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll dp[32][202];
int main(){
    ll n,suma=0,sumb=0;
    scanf("%lld",&n);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=4*i;j++){
            if(j>=1) dp[i][j]+=dp[i-1][j-1];
            if(j>=2) dp[i][j]+=dp[i-1][j-2];
            if(j>=3) dp[i][j]+=dp[i-1][j-3];
            if(j>=4) dp[i][j]+=dp[i-1][j-4];
        }
    }
    for(int i=3*n;i<=4*n;i++) suma+=dp[n][i];
    sumb=pow(4,n);
    printf("%lld/%lld\n",suma/__gcd(suma,sumb),sumb/__gcd(suma,sumb)); //这里使用了内置的__gcd()函数（即gcd前面加两条下划线）
    return 0;
}