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

求方法个数，时间给了1s于是不得不放弃暴力的想法（qaq)那就dp！ 先想总的方法数：显然是4的n次方，那么我们就在找一下不会亏本的方法数，求一下gcd，输出答案就好了。

状态表示：我的状态表示比较麻烦（写完之后看了别的佬的代码）用了三维。

dp[i][j][k],i表示买了i张，j为当前这张的中奖金额，k为盈利了多少，dp[i][j][k]为方法数。

状态计算：显然每张彩票都要用上，所以只能由前一张彩票转移而来，那前一张的盈利数额应该为k-（j-3）即当前盈利数额减去这张的盈利额，于是状态转移方程就有了：

dp[i][j][k]=dp[i-1][1][k-(j-3)]+dp[i-1][2][k-(j-3)]+dp[i-1][3][k-(j-3)]+dp[i-1][4][k-(j-3)]

由于可能亏本，所以k的值可能为负值，所以我们给k统一加上一个定值让其不为负。上代码：

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dp[31][5][101]={0};
void solve(){
    int n;
    cin>>n;
    if(n==0){
        cout<<1<<'/'<<1;
        return;
    }//n==0需要特判。
    int w=2*n;//加上w让盈利值不为负
    dp[1][1][w-2]=1;
    dp[1][2][w-1]=1;
    dp[1][3][w]=1;
    dp[1][4][w+1]=1;//初始化
    for(int i=2;i<=n;i++){
        for(int j=1;j<=4;j++){
            for(int k=-(2*i);k<=i;k++){
                dp[i][j][k+w]=dp[i-1][1][k+w-(j-3)]+dp[i-1][2][k+w-(j-3)]+dp[i-1][3][k+w-(j-3)]+dp[i-1][4][k+w-(j-3)];//转移方程
            }
        }
    }
    int h=n;//h为最多盈利数
    ll ans=0;
    for(int i=1;i<=4;i++){
        for(int j=w;j<=w+h;j++) ans+=dp[n][i][j];//把1到4元的方法数加起来即为答案。
    }
    ll sum=1;
    for(int i=1;i<=n;i++) sum*=4;//sum为总方法数
    ll c=gcd(ans,sum);
    ans/=c;
    sum/=c;
    cout<<ans<<"/"<<sum;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}




js