零基础学jsp网站开发,湖南手机版建站系统信息,长沙楼盘信息官网,网站建设认证试题题意 题目链接 求出把$n$分解为斐波那契数的方案数#xff0c;方案两两不同的定义是分解出来的数不完全相同 Sol 这种题#xff0c;直接爆搜啊。。。 打表后不难发现$1e18$的fib数只有88个 最先想到的应该是直接把$n$加入到搜索状态里#xff0c;然后枚举能被分成哪些 但…题意 题目链接 求出把$n$分解为斐波那契数的方案数方案两两不同的定义是分解出来的数不完全相同 Sol 这种题直接爆搜啊。。。 打表后不难发现$1e18$的fib数只有88个 最先想到的应该是直接把$n$加入到搜索状态里然后枚举能被分成哪些 但是这样分解出来的数可能会有重复的因此我们还要把当前考虑到第几个数也加入到状态里。 不难得到以下代码 但是很显然会T飞。 优化一下只考虑当前的fib数对答案的贡献 也就是搜两种情况 1、用该数分解 2、不用该数分解 代码是这样的 然而还是会T飞。 继续剪枝。 根据斐波那契的性质$\sum_{i 1}^n f_i f_{n2} -1$ 因此我们想要用前$ti - 1$个合成$x$必须满足$x f_{ti1}$。 然后就A了qwq // luogu-judger-enable-o2
#includecstdio
#includeiostream
#includemap
#define Pair pairint, 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;
mapPair, 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;
}
