洛谷P4133 [BJOI2012]最多的方案(记忆化搜索)

题意

题目链接

求出把$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

#include

#include

#define Pair pair

#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 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;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!