题目传送门:小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; }
Comments NOTHING