洛谷P4133 [BJOI2012]最多的方案(记忆化搜索)
2018-09-18 06:25:31来源:博客园 阅读 ()
题意
题目链接
求出把$n$分解为斐波那契数的方案数,方案两两不同的定义是分解出来的数不完全相同
Sol
这种题,直接爆搜啊。。。
打表后不难发现$<=1e18$的fib数只有88个
最先想到的应该是直接把$n$加入到搜索状态里,然后枚举能被分成哪些
但是这样分解出来的数可能会有重复的,因此我们还要把当前考虑到第几个数也加入到状态里。
不难得到以下代码
但是很显然会T飞。
优化一下,只考虑当前的fib数对答案的贡献,
也就是搜两种情况:
1、用该数分解
2、不用该数分解
代码是这样的
然而还是会T飞。
继续剪枝。
根据斐波那契的性质$\sum_{i = 1}^n f_i = f_{n+2} -1$
因此我们想要用前$ti - 1$个合成$x$,必须满足$x < f_{ti+1}$。
然后就A了qwq
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<map> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second #define int long long #define ull unsigned long long using namespace std; const int MAXN = 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int f[MAXN], tot, lim, dp[MAXN], N; map<Pair, int> mp; int dfs(int x, int ti) { if(mp.find(MP(x, ti)) != mp.end()) return mp[MP(x, ti)]; if(x == 0) return 1; int ans = 0; /*for(int i = ti; i >= 1; i--) { if(x - f[i] >= 0) ans += dfs(x - f[i], i - 1); //else break; }*/ if(x - f[ti] >= 0) ans += dfs(x - f[ti], ti - 1); if(x < f[ti + 1]) ans += dfs(x, ti - 1); return mp[MP(x, ti)] = ans; } main() { lim = 1e18; f[1] = 1; f[2] = 2; for(int i = 3; i; i++) { f[i] = f[i - 1] + f[i - 2]; if(f[i] > lim) {tot = i; break;} } N = read(); //dp[0] = 1; cout << dfs(N, tot - 1); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++系统学习之九:顺序容器
下一篇:NOIP复习之1 数学数论
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash