动态规划

题意：

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

分析：

首先我想到的动态规划是：
dp[i][j] 表示在买第i次的时候总共中奖金额j的概率！
那么这个是很好求的：
dp[i][j] = (dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4])/4
但是题目目中不仅让我们输出概率，还让我们以最简分式形式输出。
那么我们采用这种方式就会麻烦许多。
重新定义：
dp[i][j] 表示在买第i次的时候总共中奖金额是j的所有方案
在于概率相关的题目中求所有方案数，这很常见。
那么：
dp[i][j] = dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]
要注意的是第i次的时候中奖金额的可能为[i,i*4]
所以，状态转移时要留心

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int max_n = 33;
const int max_v = max_n * 4;
ll dp[max_v];
int n;

ll gcd(ll a, ll b) 
{
    if (b == 0)return a;
    return gcd(b, a % b);
}

pii besim(pii p) 
{
    ll a = p.first;
    ll b = p.second;
    ll mid = gcd(a, b);
    while (mid!=1) 
    {
        a /= mid;
        b /= mid;
        mid = gcd(a, b);
    }
    return { a,b };
}

int main() 
{
    ios::sync_with_stdio(0);
    cin >> n;
    dp[0] = 1;
    for (int i = 1;i <= n;i++) 
    {
        for (int j = i * 4;j >= i;j--)
        {
            ll tmp = 0;
            for (int k = 1;k <= 4;k++) 
            {
                if (j - k < i - 1 || j - k > i * 4 - 4) continue;
                tmp += dp[j - k];
            }
            dp[j] = tmp;
        }
    }
    pii ans;
    for (int i = n;i <= n * 4;i++)
        ans.second += dp[i];
    for (int i = n * 3;i <= n * 4;i++)
        ans.first += dp[i];
    ans = besim(ans);
    cout << ans.first << "/" << ans.second << endl;
}