ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年2月23日 698点热度 0人点赞 0条评论

题目传送门:小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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP 动态规划 牛客网
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号