[BJOI2012]最多的方案（记忆化搜索）-白红宇

[BJOI2012]最多的方案（记忆化搜索）

阅读量：5145 次

发布时间：2019-06-13

本文共 942 字，大约阅读时间需要 3 分钟。

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

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

显然要记忆化搜索。

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

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

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

Code

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

转载于:https://www.cnblogs.com/ZH-comld/p/9693575.html

你可能感兴趣的文章