【牛客23413】小A买彩票(DP)

发布于 2022-02-23  813 次阅读


题目传送门:小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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09