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

时间:2023-03-08 19:55:08

第二关和很出名的斐波那契数列有关,地球上的OIer都知道:F1=1, F2=2, Fi = Fi-1 + Fi-2,每一项都可以称为斐波那契数。现在给一个正整数N,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数,那么对一个N最多可以写出多少种方案呢?

题意是说数列中不能出现相同的数。

显然要记忆化搜索。

直接搜会T,我们枚举下一个数填什么是要从大到小枚举,可以使效率有指数级的提升。

这是枚举上界,枚举下界可以用前缀和+二分来优化枚举复杂度。

加了这两个优化后代码跑的飞快。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define mm make_pair
using namespace std;
typedef long long ll;
ll dp[],sum[];
map<pair<ll,int>,ll>mem;
ll n;
ll dfs(ll x,int xian){
if(!x)return ;
if(mem[mm(x,xian)])return mem[mm(x,xian)];
ll ans=;
int p=lower_bound(sum+,sum++,x)-sum;
for(int i=p;i<=xian;++i)if(dp[i]<=x)ans+=dfs(x-dp[i],i-);else break;
return mem[mm(x,xian)]=ans;
}
int main(){
scanf("%lld",&n);dp[]=dp[]=;
for(int i=;i<=;++i)dp[i]=dp[i-]+dp[i-];
for(int i=;i<=;++i)sum[i]=sum[i-]+dp[i];
printf("%lld",dfs(n,));
return ;
}