【牛客23413】小A买彩票（DP）

题目传送门：小A买彩票

思路

观察数据范围 0 <= n <= 30，如果使用搜索的话，复杂度是O(2 ^ N)显然不行，因为这里的每个状态（购买彩票的数量）之间是有关联的，所以考虑DP，但是这个DP不是线性的。

既然知道是DP，那么就需要给每个状态一个准确的定义，这时候有个小技巧就是观察数据范围，n最大为30，30的平方不会超，30的三次方也不会超，所以我们的dp数组可能是二维或者三维。

收益（不算成本）的范围是[n, 4n]，那么我们可以开一个二维数组，其中dp[i][j]表示买i张彩票，收益为j的方案数，只需要枚举得到dp[n][3n ~ 4n]求和，就可以得到所有不亏本的方案数，答案的分子就是这个，分母就是总方案数2 ^ n。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
//全局变量开始
const int maxn = 40;
int N;
int dp[maxn][121];//dp[i]表示买 i 张且 收益为 j 的方案数
//全局变量结束
inline int gcd(int a,int b){return a == 0 ? b : gcd(b % a, a);}
inline int qmi(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res *= a;	
		a *= a, b >>= 1;
	}
	return res;
}
signed main()
{
	//freopen("in.txt","r",stdin);
	N = re();
	dp[0][0] = 1;
	for(int i = 1;i <= N; ++ i)//买 i 张 
	{
		for(int j = i;j <= 4 * i; ++ j)//收益为 j 范围是[i, 4i]
		{
			for(int l = 1;l <= 4 && j - l >= 0; ++ l)
				dp[i][j] += dp[i - 1][j - l];
		}
	}
	int cnt = 0;
	for(int i = 3 * N; i <= 4 * N; ++ i)cnt += dp[N][i];
	int tot = qmi(4, N);
	int g = 1;
	while((g = gcd(cnt, tot)) != 1)cnt /= g, tot /= g;
	pr("%lld/%lld\n",cnt,tot);
	return 0;
}